supertables-3

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.

Source: hackerearth | Difficulty: MEDIUM
Tags: Sorting

Mathematics


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
from fractions import gcd
t=eval(input())
while t>0:
	t-=1
	a,b,n=list(map(int,input().split()))
	c=(a*b)/(gcd(a,b))
	l,r=1,1000000000000
	while(l<=r):
		m=(l+r)/2
		s=m/a+m/b-m/c
		if (s==n):
			print(max((m/a)*a,(m/b)*b))
			break
		elif (s<n):
			l=m+1
		else:
			r=m-1
			


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
from fractions import gcd
t=eval(input())
while t>0:
	t-=1
	a,b,n=list(map(int,input().split()))
	c=(a*b)/(gcd(a,b))
	l,r=1,1000000000000
	while(l<=r):
		m=(l+r)/2
		s=m/a+m/b-m/c
		if (s==n):
			print(max((m/a)*a,(m/b)*b))
			break
		elif (s<n):
			l=m+1
		else:
			r=m-1