Problem Description

The integer $ 9 $ has an interesting property. For any non-negative integer $ N $, the remainder when $ N $ is divided by $ 9 $ is the same as the remainder when the sum of the digits of $ N $ in base $ 10 $ is divided by $ 9 $.

Takahashi was curious if there were any other integers with this property. Unfortunately, the only integers found with this property were $ 9 $, $ 3 $, and $ 1 $. Therefore, he decided to relax the condition from "for any non-negative integer $ N $" to "for as many non-negative integers $ N $ as possible" and started searching under this relaxed condition.

Takahashi wants to know how many non-negative integers $ N $ satisfy the above condition for a given non-negative integer $ K $.

To help Takahashi, please answer the following question:

• Among the integers $ N $ such that $1 \leq N \leq M$, find the number of $ N $ where the remainder when $ N $ is divided by $ K $ is the same as the remainder when the sum of the digits of $ N $ in base $ 10 $ is divided by $ K $.

Input Format

The input is given from the standard input in the following format:

$ K $ $ M $

Output Format

Output the number of non-negative integers that match the condition mentioned in the problem statement in one line.

Sample Input and Output

Sample Input #1

5 100

Sample Output #1

19

Sample Input #2

112 32279

Sample Output #2

309

Sample Input #3

108 3141592653

Sample Output #3

261799999

Sample Input #4

9 10000000000

Sample Output #4

10000000000

Notes/Hints

Constraints

• All given numbers are integers.
• $1 \leq K \leq M \leq 10^{10}$

Partial Points

This problem has partial points.

• If you solve the dataset where $1 \leq M \leq 10^5$, you will get $ 10 $ points.
• If you solve the dataset where $1 \leq M \leq 10^{10}$, you will get an additional $ 90 $ points, totaling $ 100 $ points.

Sample Explanation 1

Single-digit integers always satisfy the condition. Additionally, all integers $50 \leq N \leq 59$ satisfy the condition. No other integers under $ 100 $ satisfy the condition. Therefore, output $ 19 $.

见题面 Input 部分

见题面 Output 部分