How Many Calls?

The Fibonacci numbers are defined by the following recurrence:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n – 1) + fib(n – 2)

But we're not interested in the Fibonacci numbers here. We would like to know how many calls does it take to evaluate the n-th Fibonacci number if we follow the given recurrence. Since the numbers are going to be quite large, we'd like to make the job a bit easier for you. We only need the last digit of the number of calls, when this number is represented in base b.

Input Specification

The input consists of several test cases. For each test case, you'll be given two integers n (0 ≤ n < 2⁶³ – 1) and b (1 < b ≤ 10000). The input is terminated by a test case where n = 0 and b = 0, you must not process this test case.

Output Specification

For each test case, print the test case number first. Then print n, b, and the last digit (in base b) of the number of calls. There should be a single space between two numbers of a line.

Note that the last digit has to be represented in decimal number system.

Sample Input

1. 0 100
2. 1 100
3. 2 100
4. 3 100
5. 10 10
6. 0 0

download as text file

Output for Sample Input

1. Case 1: 0 100 1
2. Case 2: 1 100 1
3. Case 3: 2 100 3
4. Case 4: 3 100 5
5. Case 5: 10 10 7

download as text file