## 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.

Sample input:
2
5
2
3
2
3
4
Sample output:
2
-1

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}

int main(){
int t;
scanf("%d",&t);
while(t--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c>max(a,b)||c%gcd(a,b)!=0){
printf("-1\n");
continue;
}
int acount=0,bcount=0;
int tempa=0,tempb=0;
while(true){
//cout<<tempa<<" "<<tempb<<endl;
if(tempa==c||tempb==c)break;
if(tempa==0){
tempa=a;
acount++;
continue;
}
if(tempb!=b){
int val=min(tempa,b-tempb);
tempb+=val;
tempa-=val;
acount++;
continue;
}
if(tempb==b){
tempb=0;
acount++;
continue;
}
}
tempa=0;tempb=0;
while(true){
//cout<<tempa<<" "<<tempb<<endl;
if(tempa==c||tempb==c)break;
if(tempb==0){
tempb=b;
bcount++;
continue;
}
if(tempa!=a){
int val=min(tempb,a-tempa);
tempa+=val;
tempb-=val;
bcount++;
continue;
}
if(tempa==a){
tempa=0;
bcount++;
continue;
}
}
printf("%d\n",min(acount,bcount));
}
return 0;
}
Copy The Code &

Input

cmd
2
5
2
3
2
3
4

Output

cmd
2
-1