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