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

Sample input:
2
5
2
3
2
3
4

 

Sample output:
2
-1

hide comments
masterchef2209: 2018-11-15 12:07:04

ad hoc
if anyone wants to dig deep in this question
see this MIT lecture-https://www.youtube.com/watch?v=NuY7szYSXSw
just keep in mind that we have to take min of algo on (a,b) and (b,a)

jmr99: 2018-10-29 20:17:39

Diophantine equation px+qy = r with a little bit simulation

yup123yup123_: 2018-09-12 09:40:25

Frankly,I don't know graphs.I could solve it perfectly with recursion.I wonder why graphs??

karan_yadav: 2018-07-12 12:04:40

Was searching for a better solution online (I used DP). After searching for a bit found a really elegant yet simple solution on StackOverflow, (https://stackoverflow.com/questions/17869493/advice-for-pour1-on-spoj)
Do give it a read.

mahabir10: 2018-06-13 16:28:54

i got accepted using only map and bfs

sherlock11: 2018-05-16 10:21:37

bfs will work...........but carefully examine when answer will be "-1"........otherwise enjoy "TLE"

itzsowvik: 2018-05-08 17:47:12

Isn't this problem is too much hard for beginners?

nadino: 2018-04-30 10:42:18

https://gist.github.com/psayre23/c30a821239f4818b0709

for those who are using Java and don't want a TLE

gauravgb21: 2018-04-25 17:06:32

solved it using DP!

chetan4060: 2017-12-28 12:38:51

ad-hoc problem
just see the pattern and read about
Diophantine equation ax+by = c .


Added by:adrian
Date:2004-05-31
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