read
while read n k a
do
f=f[n/=k,!n]+1
echo $[k-1?n*=k-1,f-1:n-1]
done