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

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

hide comments
2015-06-05 10:54:32 Ankush
WA with Extended GCD :/
Got AC on first try with bfs :D
2015-05-31 13:33:24 harshit sharma
cleared from todo list after 6 months :)....hint-> first solve EASY JUG
2014-12-16 13:02:21 piyush
nice question
2014-06-11 08:53:41 Ravi Kumar
Answer for 10 7 6 is 6

Process a(10) b(7)
1. Fill 10 0
2. pour 3 7
3. empty 3 0
4. pour 0 3
5. fill 10 3
6. pour 6 7

Last edit: 2014-06-11 08:56:06
2014-05-26 12:59:18 sai spoorthy
can anyone tell me how ans of 10 7 6 is 6 steps???@ALEX
2014-05-04 19:45:28 Alex
@Shantanu Banerjee no, the answer should be 1 step because of "At the beginning both vessels are empty".

Last edit: 2014-05-04 19:46:34
2014-05-04 19:39:45 Alex
@apoorvneema 6 steps

Last edit: 2014-05-04 19:40:17
2014-05-04 17:17:29 Adi Wibowo P
what's the formula please?
2014-02-15 11:59:54 Shantanu Banerjee
@Mohit if 4 2 2 , the answer should be 0
2014-01-16 15:52:59 ABHISHEK004
done using simple adhoc method ... :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.