Problem Description

JOI has a tenkey. The keys with digits from 0 to 9 are arranged as shown in the following figure. Note that there are no keys below the key with the digit 2 and the key with the digit 3.

There is also a cursor that points to one of the keys on the tenkey. Initially, the cursor points to the key with the digit 0.

In one operation, JOI can choose to do one of the following:

• Move the cursor to a key that is adjacent to the current key the cursor is pointing to, either vertically or horizontally. However, the cursor cannot be moved to a place where there is no key.
• Press the key. That is, input the digit printed on the key that the cursor is pointing to. If a digit has already been input by previous operations, the new digit is input immediately to the right of the previously input digits.

Now, JOI wants to input a positive integer that, when divided by \( M \), leaves a remainder of \( R \). Since the operations on the tenkey take time, JOI wants to input the number with the fewest possible operations.

Given \( M \) and \( R \), write a program to find the minimum number of operations JOI needs to perform.

Input Format

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

\( M \) \( R \)

Output Format

Output the minimum number of operations required to input a positive integer that, when divided by \( M \), leaves a remainder of \( R \).

Sample Input and Output

Sample Input #1

100000 13

Sample Output #1

5

Sample Input #2

4 3

Sample Output #2

3

Notes/Hints

Constraints

• \( 2 \leq M \leq 100,000 \).
• \( 1 \leq R < M \).
• All values in the input are integers.

Subtasks

1. (30 points) \( M = 100,000 \).
2. (70 points) No additional constraints.

Sample Explanation 1

In this example, it is possible to input 13 with the following 5 operations. Since it is impossible to input a number satisfying the condition with 4 or fewer operations, output 5.
- Move the cursor up. The key the cursor points to is now 1.
- Press the key. 1 is input.
- Move the cursor to the right. The key the cursor points to is now 2.
- Move the cursor to the right. The key the cursor points to is now 3.
- Press the key. 3 is newly input, and the digits input so far are 13.

Sample Explanation 2

In this example, it is possible to input 11 with 3 operations. Note that inputting 3 requires 4 or more operations, which is not optimal.

见题面 Input 部分

见题面 Output 部分