Description

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

Input Format

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

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

Output Format

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

99
10

2

Hint

数据范围及约定

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

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