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$.

입력 형식

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$).

출력 형식

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

예제 입력

0 1000 10
1 1000 10
0 0 0

예제 출력

Case 1: 1
Case 2: 10