问题描述

整数 $9$ 具有一个有趣的性质。无论选择哪个非负整数 $N$，$N$ 除以 $9$ 的余数与将 $N$ 表示为十进制时各位数字的和除以 $9$ 的余数是相同的。

高橋君想知道是否存在其他具有这种性质的整数。然而，不幸的是，他只找到了 $9$、$3$ 和 $1$ 这样的整数。因此，他决定放宽条件，尽可能多地寻找满足这种性质的非负整数 $N$。

高橋君想知道非负整数 $K$ 有多少个非负整数 $N$ 满足上述条件。

请回答以下问题以帮助高橋君。

• 求在满足 $1 \le N \le M$ 的整数 $N$ 中，满足 $N$ 除以 $K$ 的余数与将 $N$ 表示为十进制时各位数字的和除以 $K$ 的余数相等的个数。

---

约束条件

• 给定的数字都是整数
• $1 \le K \le M \le 10^{10}$

输入

输入以以下格式从标准输入中给出。

$K$ $M$

---

部分得分

本问题设有部分得分。

• 对于满足 $1 \le M \le 10^5$ 的数据集，给出正确答案可以获得 10 分。
• 对于满足 $1 \le M \le 10^{10}$ 的数据集，给出正确答案可以额外获得 90 分。总共可获得 100 分。

输出

请以一行输出满足问题描述条件的非负整数的个数。

---

示例输入1

5 100

示例输出1

19

一位数肯定满足条件。除此之外，所有满足 $50 \le N \le 59$ 的整数也都满足条件。除此之外，没有其他满足条件的整数在 $100$ 及以下的范围内。因此输出为 $19$。

---

示例输入2

112 32279

示例输出2

309

---

示例输入3

108 3141592653

示例输出3

261799999

---

示例输入4

9 10000000000

示例输出4

10000000000