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$