Problems
Digit
Digit
\textbf{a}
\textbf{S}
\textbf{(}
\textbf{a}
\textbf{)}
\textbf{l}
\textbf{L}
\textbf{(}
\textbf{a}
\textbf{)}
\textbf{k}
\textbf{S}
\textbf{^k}
\textbf{(}
\textbf{a}
\textbf{)}
\textbf{l}
\textbf{−1}
a
\textbf{L}
\textbf{(}
\textbf{a}
\textbf{)=}
\textbf{N}
\textbf{N}
\textbf{a}
m
For a positive integer , let be the sum of the digits in base . Also let\textit{\textbf{ }} be the minimum such that \textit{\textbf{ }}is less than or equal to . Find the minimum such that for a given , and print \textit{\textbf{ modulo }}.
\InputFile
\textbf{N}
\textbf{m}
\textbf{l}
\textbf{0}
≤
\textbf{N}
≤ \textbf{10}
\textbf{^5}
^\{ \}
\textbf{1}
≤
\textbf{m}
≤
\textbf{10}
\textbf{^9}
\textbf{2}
≤
\textbf{l}
≤
\textbf{10}
\textbf{^9}
The input contains several test cases, followed by a line containing "\textbf{0 0 0}". Each test case is given by a line with three integers , , (, , ).
\OutputFile
\textbf{a}
m
For each test case, print its case number and the minimum \textit{\textbf{ modulo }} as described above.
Input example #1
0 1000 10 1 1000 10 0 0 0
Output example #1
Case 1: 1 Case 2: 10