Given two numbers a and b, you have to find the \(N^{th}\) number which is divisible by a or b.

Input :

First line consists of an integer T, denoting the number of test cases.
Second line contains three integers a, b and N .

Output :

For each test case, print the \(N^{th}\) number in a new line.

Constraints :

\(1 \le t \le 10^5\)

\(1 \le a ,b \le 10^4\)

\(1 \le N \le 10^9\)