Find the largest LCM
Time Limit:4S Memory Limit:5120K

Description
I believe that most of you know how to split a positive integer N into the sum of several positive integers, such that their product is the biggest. We only shall try best to split N into the sum of multiple 3.
Then, how about splitting N such that their Least Common Multiplier (LCM) is the biggest?

Input
Input contains several test cases.
Each case has only one line, consisting of two positive integers, N and M. (0 < N <= 3000, 0 < M <= 10000)
The last case is followed by a line containing two zeros.

Output
The output for each case contains the biggest LCM's mod M.

Sample Input

6 23
6 23
0 0

Sample Output

Case 1: 6
Case 2: 6

谁能解决?