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:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from fractions import gcd

def b(A,B,N):
	value = max(A,B)*N
	solve2(A,B,N,value,1)

def solve(A,B,N,maxval,minval):
	midvalue = (maxval+minval)/2
	p=gcd(A,B)
	p = (A*B)/p;
	terms = midvalue/A + midvalue/B - midvalue/p
	if terms == N:
		print max((midvalue/A)*A, (midvalue/B)*B);
	elif terms > N:
		solve(A,B,N,midvalue,minval)
	else:
		solve(A,B,N-terms,maxval,midvalue)
		
def solve2(A,B,N,R,L):
	p=gcd(A,B)
	p = (A*B)/p;
	while L <= R :
		M = (L+R)/2;
		val = M/A + M/B - M/p;
		if val == N :
			print max((M/A)*A, (M/B)*B);
			break
		elif val < N :
			L = M+1;
		else:
			R = M-1;

        
if __name__ == '__main__':
	T = int(raw_input().strip())
	count=0
	while count < T :
		try:
			S = raw_input().strip()
		except EOFError:
			break
		temp = S.split()
		b(long(temp[0]),long(temp[1]),long(temp[2]))
		count=count+1