Staircase Climb Ways

You are given a staircase with n steps. Your task is to compute the number of unique ways to climb the staircase if you can take either one step or two steps at a time. Specially, when n is 0, there are 0 ways to climb the staircase.

The recurrence relation for this problem is given by:

$$dp[n] = dp[n-1] + dp[n-2]$$

with the base conditions:

• $$dp[0] = 0$$
• $$dp[1] = 1$$
• $$dp[2] = 2$$

In addition, you will be provided with a sequence of non-negative integers. Process the sequence until you encounter a 0, and for each number (except the terminating 0), output the result in the format Case #i: r, where i is the test case number (starting from 1) and r is the number of ways to climb the staircase for that given number of steps.

inputFormat

The input is given on a single line containing a list of integers separated by spaces. Each integer represents the number of steps in the staircase. The list is terminated by the integer 0, which should not be processed.

outputFormat

For each test case (each number before the terminating 0), output one line in the following format: Case #i: r, where i is the test case number (starting from 1) and r is the number of unique ways to climb that staircase.

## sample

3 5 0

Case #1: 3
Case #2: 8

</p>