Xiao Ming and Xiao Hua have two bags, which can store “ACM” books. Each bag has a maximum volume (the maximum number of books it can store). To be mentioned, the volume number is a positive integer. They have the following three operations:
(1) “Drop” Operation: Drop out all of the books from one bag.
(2) “Add” Operation: Continuously add books to one bag until reaching its maximum volume.
(3) “Transfer” Operation: Transfer books from A to B or transfer books from B to A, the number of the transferred books should be as large as possible. If the number reaches the maximum volume of B bag, then the remaining books will still stored in A bag.
Now, there are two bags A and B, the maximum volume of each is a and b. The initial values of them are both 0. We hope to reach the following state by minimum number of operations:
VA = c or VB = c
In which,VA / VB means the current number of books in bag A / B.c is a positive integer. So what is the minimum number of operations m? If the state can not be satisfied anyway, then
m= 0.
The first line is the number of test cases T. (0 < T < 100)
The next following T lines are three numbers a, b, c.
(0< a, b, c<1e9)
For each test case, we should output the corresponding answer m.