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
apoorvneema:
20131228 09:14:54
what is ans of 10 7 6 or,


candide:
20130729 23:02:50
For very fast solving, Diophantus is your friend. 

Globussoft:
20130328 07:11:30
yes are there above statement is correct 

Rishabh:
20130310 17:35:33
my code seems to be going into an infinite loop giving a tle,any tight test cases 

Ouditchya Sinha:
20130302 09:01:57
Great problem... :) I couldn't have figured it out easily, kudos to forum. 

blessed :
20130121 05:51:51
Last edit: 20130121 05:54:49 

abc:
20120801 13:43:57
when do I nedd to empty a vessel ?


Avinash Bukkittu:
20120229 20:07:28
Can you please provide some more test cases? 

Mohit:
20120216 07:31:49
@agam : der can be odd numbered solutions. for e.g 4 2 2 ans is 1


Agam Kapur:
20111124 04:06:21
there will not be a solution in two cases:

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 