non天平

题目背景

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

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

99
10

输出样例 #1

2

说明

### 数据范围及约定 对于 $30\%$ 的数据点,$m \le 2^{63}-1$。 对于 $100\%$ 的数据点,$0 \le m \le 10^{10000}$,$0<n \le 10000$。