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
apoorvneema: 2013-12-28 09:14:54

what is ans of 10 7 6 or,
any terminating condition

Last edit: 2013-12-28 09:16:07
candide: 2013-07-29 23:02:50

For very fast solving, Diophantus is your friend.

Globussoft: 2013-03-28 07:11:30

yes are there above statement is correct

Rishabh: 2013-03-10 17:35:33

my code seems to be going into an infinite loop giving a tle,any tight test cases

Ouditchya Sinha: 2013-03-02 09:01:57

Great problem... :) I couldn't have figured it out easily, kudos to forum.

blessed : 2013-01-21 05:51:51

Last edit: 2013-01-21 05:54:49
abc: 2012-08-01 13:43:57

when do I nedd to empty a vessel ?

Avinash Bukkittu: 2012-02-29 20:07:28

Can you please provide some more test cases?

Mohit: 2012-02-16 07:31:49

@agam : der can be odd numbered solutions. for e.g 4 2 2 ans is 1

@sreenatha answer shud be 20 not 0

Agam Kapur: 2011-11-24 04:06:21

there will not be a solution in two cases:
1. c > max(a,b)
2. if max(a,b) is a multiple of min(a,b) and c is not a multiple of min(a,b)
also there cant be any odd numbered solutions.
are the above statements correct ?


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