Digit Sum 2.5

問題文

$10$ 進法で整数 $N$ が与えられます。
$k$ を $2$ 以上の任意の正整数とします。$N$ を $k$ 進法で表記したときの桁和のうち最小のものを求めてください。

制約

• $0\leq N \leq 10^9$ 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

9

出力例1

1

例えば、$k=3$ のとき桁和が最小となります。 $N$ を $3$ 進法で表記すると $100$ となり、桁和は $1+0+0=1$ なので $1$ が答えです。