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 .
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 , , (, , ).
a
m
For each test case, print its case number and the minimum modulo as described above.