Farmer Jon has two cows. He loves his cows very much. One cow gives exactly A liters milk in a day. Other cow gives exactly B liters milk in a day. But Farmer Jon is a very busy person. He can collect one cow’s milk in a day.

Nowadays farmer Jon need a little bit more money to create a nice house for his cows. So he wants to sale exactly N liters milk to the buyer.

Now Farmer Jon asked to you to calculate what is the minimum days needed to make exactly N liters of milk.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains three integers A, B (1 ≤ A,B ≤= 15) and N (1 ≤ N ≤ 10⁵).

Output

For each case, print the case number and the minimum number of days needed to make exactly N liters of milk. If it is not possible to make exactly N liters of milk print “Not Possible” (without quotes)

 Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology