Equal Blood

A group of soldiers is called a Battalion. A Battalion of size S has S soldiers , and each soldier can carry at most A weapons. Basically, a Battalion is an array of size S such that the ith element represents the number of weapons carried by the ith soldier. So , for a particular size S and A, there can be many Battalions. Two Battalions of size S can be considered different if there is at least one position "i" in both the arrays such that the number of weapons carried by the soldiers in the ith position is different.

ex: Consider S = 2 and A = 2
The possible Battalions are:

[0,0] , [0,1] , [0,2] , [1,0] , [1,1] , [1,2] , [2,0] , [2,1] ,[2,2]

Watson has, under his command, all possible Battalions of size W (all of which is unique) and each soldier can carry at most A weapons.

Similarly Moriarty has, all possible Battalions of size M (all of which is unique) and each soldier can carry at most A weapons.

But both Watson and Moriarty discards the Battalions from their respective sets in which each soldier carries no weapon.

Now for the purpose of War, Watson forms SuperBattalion from his remaining Battalions such that:
1. Each SuperBattalion is a group of Battalions under his command.
2. Each SuperBattalion has equal number of Battalions ,say L1.
3. No soldier from one Battalion can be transferred to other.
4. Each Battalion is a part of exactly one SuperBattalion.

Similarly, Moriarty forms SuperBattalions each of size L2, with each of his Battalion having size M.

Both Watson and Moriarty believe in Equality and Bloodshed and to impose these concepts they agree upon the following rules.

1 . L1 should be equal to L2.
2. L1 (=L2) should be maximum possible.

Your task is to find L1.

Input Format:
The first line contains T, the number of test-cases.
Next T lines will contain three space separated integers in the format W, M and A.
Output Format:
For each test-case print a single integer L1 ,in a newline.
Constraints:

• $1 \le T \le 10^{5}$
• $2 \le W \le 10^{18}$
• $2 \le M \le 10^{18}$
• $2 \le A \le 10^{5}$