POUR1  Pouring water
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.
Input
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.
Output
For each set of input data, output the minimum number of steps required to obtain c litres, or 1 if this is impossible.
Example
2 5 2 3 2 3 4Sample output:
2 1
hide comments
Shreya Inamdar:
20110628 09:53:21
Any strong test cases or commonly overlooked impossible cases?


LeppyR64:
20110416 23:53:24
The four needs to be in one cup, not split between the two. 

S:
20110305 21:03:35
y cant we get 4 from 2 and 3


multisystem:
20110301 21:18:23
@pengzuojie


jack Wilshere:
20110223 09:18:50
In the following, ab (Current volume occupied in a&b litre containers respectively)


sreenatha:
20110217 17:41:41
i think the answer for a=12 b=11 and c=6 is zero.if anyone thinks otherwise,please post ur answer


.::Manish Kumar::.:
20101211 18:59:03
can the answer be odd number?


pengzuojie:
20100722 09:27:44
I can't believe it that when I used BFS, I got the TLE,but when I change from bfs to simulate, it's just spent 10ms,what amazing... 

madhav:
20100506 21:18:20
check out the forum guys. We have good solutions for this problem and hence a lot to learn from this problem :) Last edit: 20100506 21:19:32 

hussein:
20100418 15:04:17
BFS and a bit of math to prune impossible cases will suffice :) 
Added by:  adrian 
Date:  20040531 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  An ancient problem, formulated in these words by Mr Tadeusz Ratajczak 