POUR1 - Pouring water

现在你有两个桶，分别可以装$a,b$ 升水，请求出正好倒出$c$ 升水需要多少步。 以下的几个操作视为一个“步骤”： ·倒出桶中的水。 ·用水填满桶。 ·将水从一个桶倒入另一个桶，直到某个桶变空或变满。 输入输出格式： 输入格式： 一个整数$t$ ($1<=t<=100$ )，代表测试的用例数。接下来的$t$ 组输入数据中，每组数据有三个整数$a,b,c$ （$0<a,b,c<=40000$ )。 输出格式： 输出最小步数，如果不能正好倒出$c$ 升水，则输出$-1$ 。

Given two vessels, one of which can accommodate _a_ litres of water and the other - _b_ litres of water, determine the number of steps required to obtain exactly _c_ litres of water in one of the vessels. At the beginning both vessels are empty. The following operations are counted as 'steps': - emptying a vessel, - filling a vessel, - pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

An integer _t_, 1<=_t_<=100, denoting the number of testcases, followed by _t_ sets of input data, each consisting of three positive integers _a, b, c_, not larger than 40000, given in separate lines.

For each set of input data, output the minimum number of steps required to obtain c litres, or -1 if this is impossible.

2
5
2
3
2
3
4

 

2
-1