Problem: Little Timmy is exceptionally good at math tables, so his maths teacher decided to make things a bit more interesting. His teacher takes two numbers A and B and merges the tables of A and B in sorted order (ascending order), removing the duplicates and thus creates supertable of A and B and asks Little Timmy the Nth number in the supertable.
Given A, B and N, calculate the Nth number in the supertable of A and B.

Input
First line contains number of test cases T . Each test case contains three integers A , B and N .

Output
For each test case print the N^th number of the supertable.

Constraints:
1 ≤ T ≤ 300000
1 ≤ A, B ≤ 1000
1 ≤ N ≤ 1000000000

SAMPLE INPUT
4
3 5 2
3 5 3
2 3 4
2 3 6

SAMPLE OUTPUT
5
6
6
9

Explanation

Test Case #1:

A=3, B= 5
Table of A = 3 , 6 , 9 , 12 ,15 ,18  and so on
Table of B =5 , 10 , 15 , 20  and so on 
After Merging : 3, 5, 6,  9 ,10 , 12 ,15 ,15, 18, 20   and so on
Remove Duplicates : 3 , 5 , 6, 9 , 10 , 12 , 15 , 18 , 20  and so on
For N= 2 , 2nd element of the supertable is 5 .

Test Case #2:

For N=3 , 3rd element of the supertable is 6.

Solution (in PYTHON):

Solution:
import math

def gcd(a, b):
	if b%a == 0:
		return a
	else:
		return gcd(b%a, a)
		
def find_element(a, b, n):
	if n == 0:
		return 0
	if n == 1:
		return a
	l = 0
	r = n+1
	pre = 0
	i = int(math.floor(n/2))
	while 1:
		if a * i < b * (n-i):
			if a * (i+1) < b * (n-i):
				l = i+1
				i = int(math.floor((l+r)/2))
			else:
				return b * (n-i)
		else:
			if a * i > b * ((n-i)+1):
				r = i
				i = int(math.floor((l+r)/2))
			else:
				return a * i
		
t = int(raw_input())
#gcd_dict = {}
while t > 0:
	t = t - 1
	line = raw_input().split()
	a = int(line[0])	
	b = int(line[1])
	n = int(line[2])
	if a == 0:
		print b * n
		continue
	if b == 0:
		print a * n
		continue
	if a == 1 or b == n:
		print n
		continue
	if a > b:
		temp = a
		a = b
		b = temp
	lcm = (b/gcd(a, b))*a
	period = lcm/a + lcm/b - 1
	ans = 0
	if n >= period:
		temp = int(math.floor(n/period))
		ans = temp*lcm + find_element(a, b, n - temp*period)
	else:
		ans = find_element(a, b, n)
	print ans