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
surayans tiwari(http://bit.ly/1EPzcpv):
20160710 12:47:45
0.29 sec using bfs+map and 0.00 using eea,, nice question, worth the time; 

karthik1997:
20160618 19:19:55
Used Unordered_map and fast I/o with BFS ,... and I couldnt get below 0.08s ... But when I just space optimized it a bit ... Got AC in 0.00s :D Hip hip hurray 

nightwolf_9197:
20160518 16:06:00
@nguyenthanhloc: 5 2 7=1


nguyenthanhloc:
20160421 04:43:53
pls tell me: out put of test case:


code_astra1:
20160128 10:52:37
Resource for solving in O(a+b) time :


bigcrunch:
20160120 07:21:30
can 0 be any of the inputs a,b or c?


vedang:
20151226 19:03:27
BFS tip : Use STL map instead of arrays. 

jpritcha:
20151007 04:00:32
A bit frustrated with this one, the solution I arrived at (C++) works for all the test cases I can find and seems to be the correct logic according to a few different posts on stackoverflow, but I keep getting WA. 

yurkoflisk:
20150824 17:30:56
AC with Diophantine equation and a bit logic :) 

Bhavuk:
20150822 20:11:15
My halfcentury! 
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 