Problem C
New Rule in Euphomia
Input: standard input
Output: standard output
Time Limit: 1 second

The ancient country of Euphomia had some strange rules regarding payment of prices and values of coins. When King Albert ruled this country the following payment rules were in place:

a) The name of the currency was Abacus.

b) Only coins were used to pay any certain amount.

c) The coins had integer values. Eg. There is no coin with value 1.5 Abacus. And the amount to be paid was also always integer.

d) There was no 1 Abacus coin.

e) Payments of any amount had to be made with coins of the same value. For example when one paid 9 Abacus he paid it with three 3-Abacus coins.

So coins were made so that any one could pay any amount within 2-1000000 abacuses following the above rules. The coins, which were not required, were not made. For example there were no 6-Abacus coin because one could pay 6 Abacus as (3+3) Abacus. The problem with the above rule was that often one had to use many coins to pay a particular amounts. For example to pay the amount 2048 Abacus one had to use 1024 2-Abacus coins which is quite terrible. Therefore, when king Lucas captured this country he made unlimited coins of value 1 Abacus and added the following rule:

“One can only use exactly two different coins made during Albert's regime. In addition with these coins one can also use the 1-Abacus coins at any number. However one cannot use only the 1-Abacus coins to make payment."

So in this new rule paying 1 Abacus is still impossible but rule d) and e) of Albert’s regime is now obsolete. With this new rule in place your job is to find out in how many ways one could pay a certain amount n.

For example one can now pay 10-Abacus in the following five ways:

a) 3+2+1+1+1+1+1

b) 7+3

c) 5+2+1+1+1

d) 7+2+1

e) 5+3+1+1

Input

The input file contains less than 600 lines of inputs. Each line of the input file contains one value of n (0<n<=1000000), which indicates the amount to be paid. Input is terminated by a line where n=0. Obviously this line should not be processed.

Output

For each line of input except the last one produce one line of output, which contains the serial of output followed by an integer which indicates in how many ways one can pay n abacus with the new rules in place. Look at the output for sample input for details.

Sample Input Output for Sample Input

996542

129

Case 1: 5

Case 2: 1661327749

Case 3: 22

Case 4: 296

Problem setter: Shahriar Manzoor, EPS

Special thanks (for alternate solution): Derek Kisman, EPS