背景

non 最近正在为自己的体重而苦恼，他想称量自己的体重。于是，他找来一个天平与许多砝码。

题目描述

砝码的重量均是 $n$ 的幂次，$n^1, n^2, n^3, n^4, n^5$ 的……non 想知道至少要多少个砝码才可以称出他的重量 $m$。注意砝码可以放左边，也可以放右边。

输入格式

第一行一个正整数 $m$，表示 non 的重量；

第二行一个正整数 $n$，表示砝码重量幂次的底。

输出格式

一个整数表示最少所需的砝码数。

99
10

2

提示

数据范围及约定

对于 $30\%$ 的数据点，$m \le 2^{63}-1$。

对于 $100\%$ 的数据点，$0 \le m \le 10^{10000}$，$0<n \le 10000$。