Walk Alone is thirsty and he wants to drink water. He wants to drink exactly units of water, but he does not have an appropriate measuring cup. He only has two water bottles of volume and 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 and units of water respectively, he can only transfer water from to or from to .

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 units of water?

输入描述:

The input contains multiple test cases.
The first line of the input contains an integer , the number of test cases.
Each test case contains only one line with three integers , 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  units of water, output .

5
2 5 1
2 3 7
4 6 3
3 13 8
12 9 6

5
6
-1
15
5

备注:

In the first example, Walk Alone will do the following operations:
1. Fill the second bottle.
2. Transfer  units of water from the second bottle to the first one.
3. Spill all water from the first cup.
4. Transfer  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.