题目描述

给定正整数 $n, b$ ，求所有 $n$ 的正整数倍数中 $b$ 进制表示下非零位个数的最小值。

输入格式

一行两个正整数 $n, b$ 。

输出格式

一行一个正整数，表示答案。

输入样例1

79 2

输出样例1

3

样例1解释

可以发现 79 的所有正整数倍数中， 2 进制表示下非零位的个数不少于为 3 。而 $13 \times 79=1027=(10000000011)_{2}$

输入样例2

9982443 53

输出样例2

2

测试点约束

对于所有测试点： $1 \leq n \leq 10^{7}, 2 \leq b \leq 10^{7}$ 。 对于20%的数据，$n \leq 10^{3}$ 对于40%的数据，$n \leq 9*10^{4}$ 对于另外30%的数据，保证$b=2$ 对于100%的数据，满足原始限制