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
shiva890:
20220107 05:36:59
I got tle happy 

amolmawale813:
20211024 20:37:07
How could we get it's answers??


haiderbaig:
20200906 12:23:37
AC in BFS and unordered_maps to mark visited nodes/states


pb_81:
20200610 17:55:01
can anyone please give some corner test cases. As it is difficult to debug without it. I also tested so many cases but did not find the error! 

apoorva222g:
20200329 09:26:37
You must simulate by doing "pouring action" only in one jug and "discharging action" only in the opposite jug.


importme:
20200311 14:41:16
Some optimisations necessary for while using BFS, otherwise TLE. Good question! 

parsabn:
20191022 15:44:09
good question .


eagleshadow:
20190525 12:59:49
Nice Question! 

abhinav_jain02:
20181221 13:00:35
Good question to ponder. Finally AC using concept of Diophantine equation 

masterchef2209:
20181115 12:07:04
ad hoc

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 