Interesting Yang Hui Triangle

Time Limit: 1000MS

Memory Limit: 65536K

Description

Harry is a Junior middle student. He is very interested in the story told by his mathematics teacher about the Yang Hui triangle in the class yesterday. After class he wrote the following numbers to show the triangle our ancestor studied.
1
11
121
1331
14641
15101051
1615201561
172135352171
……

Input

There are multiple test cases in the input file. Each test case contains two numbers P and N, (P < 1000, N ≤ 109), where P is a prime number and N is a positive decimal integer.P = 0, N = 0 indicates the end of input file and should not be processed by your program.

Output

For each test case, output the last four digits of the number of elements on the N + 1 line on Yang Hui Triangle which can not be divided by P in the format as indicated in the sample output.

Sample Input

3 4
3 48
0 0

Sample Output

Case 1: 0004
Case 2: 0012

Hint

Source

Shanghai 2006

提交代码