Marbles Problem Code: REC20A codechef Answer

 RECode 20.0 » Marbles

Marbles

Problem Code: REC20A

Add problem to Todo list

Submit

Sang-woo and Abdul Ali are teammates. Sang-woo has marbles each of worth a won and Abdul has marbles each of worth b won.

won is the currency of South Korea.

Their task is to buy a piggy bank, whose cost can be any even number greater than or equal to X.

Find the minimum number of marbles required to buy it.

NOTE: They dont have to minimise the total cost.

Input Format

The first line contains T- the number of testcases

The first line of each testcase contains three numbers- a,b,X

Output Format

For each testcase, output the minimum number of marbles required to obtain an even value ≥X in a single line.

Constraints

1≤T≤105

1≤a,b≤109

1≤X≤1012

Sample Input 1 

3

1 3 2

4 6 10

6 6 6      

  

Sample Output 1 

2

2

1

Explanation

Testcase 1: They can take two marbles of worth 1 won

Testcase 2: They can take one marble of worth 4 won and one of worth 6 won

Testcase 3: They can take any one marble to satisfy our condition

Click Here For Answer