Gift Dilemma

You all know Dr. Sheldon Cooper. Everything Sheldon gets, he must give back the same. He doesn’t want to be in someone’s debt. Another friend of Sheldon, Penny has given him a very precious gift for his birthday. What penny didn’t know, now Sheldon is going over his head to find out some gifts that will exactly match the price of Penny’s gift. So my first task was to find out the price of the gift. With my super powerful sixth sense I found out that the price was P . Now comes the hardest part. Sheldon needs to buy a gift which will cost exactly P. He went to the nearby shop for this. It is a crazy shop. Because it sells only three types of things: Rubik’s cubes, mouth organs and chocolates. The prices of them are A, B, C accordingly. Now Sheldon faces a dilemma. What to buy and how many to buy? Because it turns out he can buy things costing P in various ways. For example if, A = 202, B = 203, C = 200 and P = 606, then are two different way to buy gifts costing exactly P. The first way is buying no Rubik’s cubes, two mouth organs and one chocolate. The second way is buying three Rubik’s cubes, no mouth organs and no chocolates. Now Sheldon is asking for your help (because I am retired from contests). Given A, B, C and P, you need to find out in how many ways he can buy gifts costing exactly P . Input The first line will contain T (T ≤ 100), the number of test cases. Next T lines each will have four integers, A, B, C and P (0 < A, B, C, P ≤ 100000000) and C/ gcd(A, B, C) ≥ 200, where gcd(A, B, C) means the greatest common divisor of A, B and C. Output For each case print ‘Case C: W’ (without the quotes), where C is the case number and W is the number of ways Sheldon can buy gifts. Sample Input 1 202 203 200 606 Sample Output Case 1: 2