DBAL - Jon and Cow

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 ≤ 105).

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)

Sample Input

Output for Sample Input

3

2 3 7

2 3 12

2 2 11

Case 1: 3

Case 2: 4

Case 3: Not Possible

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


Added by:Alim
Date:2014-05-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2018-08-10 22:15:52
BFS works but O(max(A, B)) is way faster. Anyone found O(1)? Nice tutorial problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.