题目描述

给定两个正整数 $A,B$。你需要把 $A$ 表示成若干个 $B$ 的整数次幂的代数和，并使项数尽可能少。也就是说，要求

$A=s_1B^{k_1}+s_2B^{k_2}+\cdots+s_nB^{k_n}$，

其中每个 $s_i\in\{-1,1\}$，每个 $k_i$ 都是整数。求最小可能的项数 $n$。

注意，指数 $k_i$ 允许为负数。

输入格式

第一行一个正整数 $A$，没有前导零，十进制位数不超过 $3000$。

第二行一个整数 $B$，满足 $1\le B\le10^6$。

输出格式

输出最小项数 $n$。

样例

1120
10

4

数据范围

• $A$ 为不超过 3000 位的正整数；
• $1\le B\le10^6$。

时间限制： 0.25 秒
空间限制： 64 MB