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
anirudnits: 2018-10-24 07:22:22

nice problem.

dinesh_kumar23: 2018-09-20 22:18:13

No need of binary search. Simple logic, AC in first go.

shrikant_7: 2018-08-14 08:05:51

incorrect testCases... thanks @wisfaq for figuring it out.

nadstratosfer: 2018-06-12 21:36:54

Kudos to wisfaq for figuring out that the missing testcase requires reprinting the last result. Completely lame from psetter to leave something like this for solvers to handle. -1

sonuverma: 2018-01-08 06:31:21

Binary Search :-)

Nishant Gupta: 2017-12-24 21:04:44

Some input files seem to be broken which will cause Fast I/O yielding TLE.
Use scanf for input.

holmesherlock: 2017-11-05 19:39:58

very good problem :-)

mahilewets: 2017-09-16 17:05:14

Nice, I learned how to handle exceptions in Python

Aleksandar Kostadinov: 2017-09-11 21:46:55

@wisfaq: Thanks for usefull hint!

wisfaq: 2017-09-11 20:44:38

@David (and others having problems with NZEC)
One of the ways to overcome those problems is to use error handling.
Something like:
try:
__read a,b,n
__get answer(a,b,n)
__store answer
__print answer
except:
_print stored (previous) answer.
That's the way I got AC with Python

Last edit: 2017-09-11 20:48:39

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