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 4
Sample output:
2 1
hide comments
masterchef2209:
20181115 12:07:04
ad hoc


jmr99:
20181029 20:17:39
Diophantine equation px+qy = r with a little bit simulation 

yup123yup123_:
20180912 09:40:25
Frankly,I don't know graphs.I could solve it perfectly with recursion.I wonder why graphs?? 

karan_yadav:
20180712 12:04:40
Was searching for a better solution online (I used DP). After searching for a bit found a really elegant yet simple solution on StackOverflow, (https://stackoverflow.com/questions/17869493/adviceforpour1onspoj)


mahabir10:
20180613 16:28:54
i got accepted using only map and bfs 

sherlock11:
20180516 10:21:37
bfs will work...........but carefully examine when answer will be "1"........otherwise enjoy "TLE" 

itzsowvik:
20180508 17:47:12
Isn't this problem is too much hard for beginners?


nadino:
20180430 10:42:18
https://gist.github.com/psayre23/c30a821239f4818b0709


gauravgb21:
20180425 17:06:32
solved it using DP! 

chetan4060:
20171228 12:38:51
adhoc problem

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 