Walter and Jesse's friend Mike had helped them in making Crymeth and hence, they wanted to give him a share.
For deciding the share, they both decided to choose one number each, X and Y and found out that K^th Highest Common Factor of their two numbers is a good amount of Crymeth that can be given to Mike .
Walter and Jesse did this activity for D days in total. For each day, find out what quantity of Crymeth they decided to give to Mike.

Input:

First line contains a natural number D - the total number of days.
D lines follow. Each line contains three natural numbers - X, Y and K.

Output:

For each day, print the quantity given to Mike on a new line.
If the K^th HCF of X and Y does not exist, simply print "No crymeth today" (Without the quotes)

Constraints:

• 1 ≤ D ≤ 10³
  
• 1 ≤ X, Y, K ≤ 10¹⁰