For a positive integer a, let S(a) be the sum of the digits in base l. Also let L(a) be the minimum k such that S^k(a) is less than or equal to l-1. Find the minimum a such that L(a) = N for a given N, and print a modulo m.

Input

The input contains several test cases, followed by a line containing "0 0 0". Each test case is given by a line with three integers $N, m, l (0 \leq N \leq 10^5, 1 \leq m \leq 10^9, 2 \leq l \leq 10^9)$.

Output

For each test case, print its case number and the minimum a modulo m as described above.

Example

Input

0 1000 10
1 1000 10
0 0 0

Output

Case 1: 1
Case 2: 10

见题面

见题面