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
Ankush :
20150605 10:54:32
WA with Extended GCD :/


harshit sharma:
20150531 13:33:24
cleared from todo list after 6 months :)....hint> first solve EASY JUG


piyush:
20141216 13:02:21
nice question 

Ravi Kumar:
20140611 08:53:41
Answer for 10 7 6 is 6


sai spoorthy:
20140526 12:59:18
can anyone tell me how ans of 10 7 6 is 6 steps???@ALEX 

Alex:
20140504 19:45:28
@Shantanu Banerjee no, the answer should be 1 step because of "At the beginning both vessels are empty". Last edit: 20140504 19:46:34 

Alex:
20140504 19:39:45
@apoorvneema 6 steps Last edit: 20140504 19:40:17 

Adi Wibowo P:
20140504 17:17:29
what's the formula please? 

Shantanu Banerjee:
20140215 11:59:54
@Mohit if 4 2 2 , the answer should be 0 

ABHISHEK004:
20140116 15:52:59
done using simple adhoc method ... :) 
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 