很久很久以前，有一个数字加入了 UOJ 群。

这天，在它讨论“一个数字应该怎么取模”的时候一不小心被删除了，变成了被粉碎的数字。

突然间，它突然发现它忘记了自己是谁。这让它感觉很焦躁，于是它来拜托你来帮它找到它所代表的整数 $x$。

在经过一番询问之后，你整理了一下现在你得到的线索：

1. 已知整数 $R$，有 $1 \leq x \leq R$
2. 定义函数 $f(x)$ 为 $x$ 的各位数字之和，例如 $f(13)=4,f(233)=8$。已知整数 $k$，有 $f(x)=f(k \times x)$

然而遗憾的是，你发现即使拥有了这些条件，可能的 $x$ 依然有很多个。因此，为了进一步缩小排查范围，你想要知道满足这两个条件的整数有多少个。

输入格式

仅一行两个正整数 $R$ 和 $k$。

输出格式

仅一个整数，表示可能的整数 $x$ 有多少个。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

100 1

output

100

explanation

因为对于所有的正整数 $x$ 都有 $f(x)=f(x)$，所以答案就是 $R$，即100。

样例二

input

10 3

output

1

explanation

只有⑨是满足条件的。

样例三

input

666666666 233

output

15272224

限制与约定

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载