THREENUMBERS - nth number

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

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

hide comments
2017-09-11 21:46:55 Aleksandar Kostadinov
@wisfaq: Thanks for usefull hint!
2017-09-11 20:44:38 wisfaq
@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
2017-09-11 15:30:37 David N. Springer
If I check for premature EOF, I get WA otherwise I get NZEC.
Please help. How to handle missing testcase?
2017-09-11 08:27:26
easy one ..
2017-09-10 20:01:59
can anyone send me the hint or solution of this problem ??
2017-09-09 21:50:31
No editorials on SPOJ?

=(Francky)=> We keep an eye. Always.

Last edit: 2017-09-10 08:25:01
2017-09-09 21:50:01
Can someone please help me with the logic?
I tried using binary search. didnt work
2017-09-09 17:04:14 testing java
Input is wrong. I changed my program to version in which: if there is no new value in the input stream, i keep old value in variables a,b,n. Got AC.
2017-09-09 16:31:32
Test cases are correct! but this problem is copied directly :| ,plz make something by atleast some modifications :)
2017-09-09 15:57:41 testing java
My guess is that the actual number of tests is smaller than given t. If my reader does not blow up in such case, I have WA (as I'm printing nothing or some rubbish), otherwise i have NZEC. It may be the case that my program is faulty (hence WA), however I think, that there may be something wrong with the input (as change in handling cases which should not happen, change status of my submission).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.