ez-version

题目描述

Given positive integers $B$, $K$ and $n$, find a positive integer $x$ satisfying the following conditions:

• $x$ is a positive integer in base $B$.
• $x$ is a multiple of $K$.
• Among all such $x$, $\mathrm{cnt}_n(x)$ is minimized, where $\mathrm{cnt}_n(x)$ is defined as the sum of the $n$-th powers of the digits of $x$ in base $B$. For example, in base $10$, $\mathrm{cnt}_{2}(114)=1^2+1^2+4^2=18$.

Since $x$ can be very large, you only need to output the minimum value of $\mathrm{cnt}_n(x)$.

输入格式

The input contains three positive integers $B(2\leq B\leq 10^3)$, $K(2\leq K\leq 10^6)$ and $n(1\leq n\leq 10)$ on a single line, separated by spaces.

输出格式

Output a single integer, the minimum possible value of $\mathrm{cnt}_n(x)$.

样例输入 #1

2 5 1

样例输出 #1

2

样例输入 #2

10 2 1

样例输出 #2

1

样例输入 #3

99 999 2

样例输出 #3

2