8951: Water

Walk Alone is thirsty and he wants to drink water. He wants to drink exactly x units of water, but he does not have an appropriate measuring cup. He only has two water bottles of volume $A$ and $B$ respectively. He found out that he could do the following operations with the two bottles:

• Fill one of the two bottles with water.

• Spill all water from one of the two bottles.

• Drink all water from one of the two bottles.

• Transfer as much water as possible from one bottle to the other with no water overflow. Formally speaking, if the two bottles contain $a$ and $b$ units of water respectively, he can only transfer min⁡(a,B−b) water from $A$ to $B$ or min⁡(b,A−a) from $B$ to $A$.

Walk Alone wants to do as few operations as possible. Can you tell him the minimum number of operations he should do to drink exactly $x$ units of water?

The input contains multiple test cases.
The first line of the input contains an integer T (1≤T≤10^5), the number of test cases.
Each test case contains only one line with three integers A,B,x (1≤A,B,x≤10^9), the volume of the two bottles and the required volume of water he will drink, respectively.

For each test case, output the minimum number of operations in one line. If it is impossible for him to drink exactly $x$ units of water, output −1.

In the first example, Walk Alone will do the following operations:
1. Fill the second bottle.
2. Transfer 2 units of water from the second bottle to the first one.
3. Spill all water from the first cup.
4. Transfer $2$ units of water from the second bottle to the first one, after which there is exactly one unit of water in the second bottle.
5. Drink all water in the second bottle.