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