eolymp
bolt
Try our new interface for solving problems

Digit

Time limit 2 seconds
Memory limit 64 MiB

a

S

(

a

)

l

L

(

a

)

k

S

^k

(

a

)

l

−1

a

L

(

a

)=

N

N

a

m

For a positive integer , let be the sum of the digits in base . Also let be the minimum such that is less than or equal to . Find the minimum such that for a given , and print modulo .

Input data

N

m

l

0

N

10

^5

^{ }

1

m

10

^9

2

l

10

^9

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 , , (, , ).

Output data

a

m

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

Examples

Input example #1
0 1000 10
1 1000 10
0 0 0
Output example #1
Case 1: 1
Case 2: 10
Source ACM-ICPC Japan Alumni Group Spring Contest 2012 , Tokyo, Japan, 2012-04-15