Компьютерде жүйелік дыбыс \(X\), ал қосымшада — өз дыбысы \(Y\) бар. Соңғы дыбыс \(X \cdot Y\)-ға тең.

Бір әрекетте \(X\)-ты немесе \(Y\)-ны \(1\)-ге (бірақ \(0\)-ден төмен емес) азайтуға болады. Соңғы дыбыстың \(R\)-дан аспауын қамтамасыз ету керек.

Оған жету үшін минималды әрекеттер санын табыңыз.

Енгізу

Бірінші жолда бір бүтін сан \(T\) — тестілік жағдайлардың саны (\(1 \le T \le 10^4\)).

Келесі \(T\) жолда әрқайсысы үш бүтін сан \(X\), \(Y\) және \(R\) — бастапқы жүйелік дыбыс, қосымшаның дыбысы және максималды рұқсат етілген дыбыс сәйкесінше (\(0 \le X, Y, R \le 10^9\)) болады.

Шығару

Әр тестілік жағдай үшін бір сан шығарыңыз — соңғы дыбыс \(R\)-дан аспауы үшін минималды әрекеттер саны.

Мысалдар

Енгізу 1

2
5 4 12
3 3 10

Жауап 1

2
0