现在你有两个桶，分别可以装a,b 升水，请求出正好倒出c 升水需要多少步。

以下的几个操作视为一个“步骤”：

1倒出桶中的水（必须倒完）。

2用水填满桶（必须给它加满）。

3将水从一个桶倒入另一个桶，直到某个桶变空或变满。

例如一个桶能装8已经有6，另外一个桶4，这个时候是可以倒入2的水也可以到给4留下2的水。

一个整数t (1<=t<=100 )，代表测试的用例数。接下来的t 组输入数据中，每组数据有三个整数a,b,c （0\lt a,b,c\leq 40000 )。

输出最小步数，如果不能正好倒出c 升水，则输出-1 。