THREENUMBERS - nth number

no tags 

Given two numbers a and b, you have to find n-th number which is divisible by a or b.

Input

First line contains an integer T (≤ 100000), denoting number of test cases.

Second line contains 3 positive integers a, b and n. (a, b ≤ 10000, n ≤ 1000000000)

Output

Print n-th number in a new line.

Example

Input:
1
2 3 10

Output:
15

hide comments
wisfaq: 2017-09-09 15:19:48

I'm getting runtime error. (both in Python and in FPC)
If I test for a=0 or b=0 or n=0 and if so output 0 then I get wrong answer.
Clearly there is something wrong with the input file(s).

[Rampage] Blue.Mary: 2017-09-09 12:07:20

Agree with @devilwolverine. The test cases are either wrong or not satisfying the input constraints.

@BlueMary: Fixed

Last edit: 2017-09-09 12:13:02
Vipul Srivastava: 2017-09-09 11:42:50

are the test cases correct?


Added by:surayans tiwari
Date:2017-09-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:SELF