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
chachaji_harsh:
20171204 17:35:45
how is it a DP problem 

mahilewets:
20170829 20:18:26
I think BFS is bad here


arthur1991:
20170326 07:38:10
i love qianqian 

osama2003:
20170125 00:31:58
1 .. nguenthanhloc 

muneebaadil:
20170104 21:37:23
Doing through BFS+maps too. But TLE. Using the following algorithm.


flyingduchman_:
20161227 14:37:10
Actual problem: You are at the side of a river. You have a "a" liter jug and a "b" liter jug. The jugs do not have markings to allow measuring smaller quantities. How canyou use the jugs to measure "c" liter of water?


kushalanand:
20161029 23:37:15
My 69th. BFS + maps :D 

albus111:
20160916 07:23:49
Is there a math formula for this question? 

conquistador:
20160812 20:28:31
My 100th.. .Beginners believe in yourself . YOU CAN SOLVE IT. Dont rely on spojtoolkit for this question. Last edit: 20160812 21:13:54 

Rajat Sharma:
20160803 20:26:02
AC Java : GCD along with logic(if conditions)

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 