# OOPS! They did it Again...

The Aliens of the Planet Muzambaro have re-elected their universally unpopular leader. After the result was announced the disappointed newspapers of some other planets had the headline “OOPS! They did it again.” Well now it is party time in Muzambaro and so they are planning to decorate k Skyscrapers of their city with lights. The longest street of planet Muzambaro is “The Deaf Street”. The properties of this street are stated below: a) There are buildings on only one side of this street. b) The total number of buildings on this one sidecan be as many as 20000000 (20 Million). c) The distance between any two consecutive buildings is equal as shown in the figure above. But if the total number of building is less than three then this rule is not valid. The size and shape of all the buildings are the same. d) The buildings are numbered sequentially. So if the number of the leftmost building is low and the number of the rightmost building is high then there are total (high − low + 1) buildings. From these (high − low + 1) buildings they want to select k buildings to decorate with lights in the following way: a) Any two consecutive buildings of the selected buildings must be equidistant. For example if k = 4 then buildings 1, 4, 7 and 10 of the above picture can be a possible choice according to this particular rule. b) The sum of the k building numbers must be divisible by k. For example the choice 1, 4, 7 and 10 is not valid according to this particular rule as (1 + 4 + 7 + 10) = 22, which is not divisible by 4. Now given the value of low, high and k the Aliens of Planet Muzambaro wants to determine in how many ways they can choose the k buildings. They have written a brute force program to find out the answer but they know that it wont terminate even in four years!! That is why they are now asking for your help. Can you help them?

2/2 Input The input file contains less than 1001 lines of inputs. The description of each line of input is given below: Each line of input describes one particular scenario. There are three integers low, high (0 < low < high < 20000001) and k (1 < k ≤ (high − low + 1)) in each line. The meaning of low, high and k are given in the problem statement above. Input is terminated by a case where low = high = k = 0 which should not be processed. Output For each line of input you should produce one line of output. This line should contain the serial of output followed by an integer, which indicates the number of ways they can choose the k buildings. Look at the output for sample input for details. Sample Input 1 10 4 2 10 4 1 48 2 1222 2329228 2 000 Sample Output Case 1: 4 Case 2: 3 Case 3: 552 Case 4: 1354902984009