UJ01 - Save the Scofield !!

no tags 

Scofield is excellent at math tables, so T-BAG decided to make things a bit more interesting. He gives two numbers A and B and merges the tables of A and B in sorted order (ascending order), removing the duplicates and thus creates Saratable of A and B (sounds interesting) and asks Scofield the Nth number in the Saratable.

Given A, B and N, Help Scofield in finding the Nth number in the Saratable, else he will be put into Camp 22 (North Korea) by the security officer T-BAG Tongue out.

Input

First line contains number of test cases T. Each test case contains three integers A, B and N.

Output

For each test case print the Nth number of the Saratable.

Constraints

1 <= T <= 300000
1 <= A, B <= 1000
1 <= N <= 1000000000

Input:
4
3 5 2
3 5 3
2 3 4
2 3 6

Output:
5
6
6
9

hide comments
:.Mohib.:: 2015-06-11 18:17:39

Finally done.... awsm que...!! :)

Mauro Persano: 2015-06-09 02:57:20

Horrible problem statement.

Alaf Azam Khan: 2015-06-05 20:53:38

Did it in 0.35 time. :) Pandey baba ki jai.

UJtriumphsâ„¢: 2015-05-25 16:12:14

@Mohib : not working for larger test cases

:.Mohib.:: 2015-05-25 10:20:25

#UJ plzz check my submission plzzzzzzz.......

Amogh: 2015-05-24 11:41:14

nice problem :p

UJtriumphsâ„¢: 2015-05-20 10:31:09

Problem statement is simple and straight on !! No tricky cases I suppose

shubhankaryash: 2015-05-19 18:42:34

can somebody post some tricky cases???

mehmetin: 2015-05-19 10:34:55

Tables are multiplication tables.

miodziu: 2015-05-19 08:02:16

I can't understand the problem statement. What's tables od A and B? Can You give an example?


Added by:Ujjawal Dixit
Date:2015-05-09
Time limit:1s-2.841s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All