Scofield is excellent at math tables, so T-BAG decided to make things a bit more interesting. He gives two numbers A and B and merges the multiplication tables of A and B in sorted order (ascending order), removing the duplicates and thus creates Saratable of A and B (sounds interesting) and asks Scofield the Nth number in the Saratable.

Given A, B and N, Help Scofield in finding the Nth number in the Saratable, else he will be put into Camp 22 (North Korea) by the security officer T-BAG .

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 Saratable.

Constraints

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

Input:
4
3 5 2
3 5 3
2 3 4
2 3 6

Output:
5
6
6
9