자릿수 합 반복 횟수

양의 정수 $a$에 대해, $a$를 $l$진법으로 적었을 때 각 자리 숫자의 합을 $S(a)$라고 하자. 또 $S^k(a) \leq l-1$을 만족하는 가장 작은 $k$를 $L(a)$라고 하자. 여기서 $S^0(a) = a$이고, $k \geq 1$에 대해 $S^k(a) = S(S^{k-1}(a))$이다.

$N$이 주어지면 $L(a) = N$인 가장 작은 양의 정수 $a$를 구하고, 그 값을 $m$으로 나눈 나머지를 출력한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 정수 $N$, $m$, $l$이 공백으로 구분되어 한 줄에 주어진다 ($0 \leq N \leq 10^5$, $1 \leq m \leq 10^9$, $2 \leq l \leq 10^9$).

마지막 줄에는 0 0 0이 주어진다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 조건을 만족하는 가장 작은 $a$를 $m$으로 나눈 나머지이다.