题目描述

JOI 君持有一个十键键盘。该键盘上印有从 $0$ 到 $9$ 的数字键，其布局如下图所示。请注意，印有数字 $2$ 的键下方，以及印有数字 $3$ 的键下方，均不存在按键。

:::align{center} :::

此外，该键盘上还设有一个光标，用于指向键盘上排列的某一个按键。光标初始时指向印有数字 $0$ 的按键。

JOI 君每次操作可以选择执行以下任一动作：

• 将光标移动至当前光标所指按键的上下左右相邻的按键上。但不可将光标移至不存在按键的位置。
• 按下当前光标所指的按键，即输入该按键上印有的数字。若此前已输入过数字，则新输入的数字将紧跟在已输入数字的右侧。

现在，JOI 君希望使用该键盘输入一个正整数，使其除以 $M$ 的余数为 $R$。由于键盘操作需要耗时，他希望以尽可能少的操作次数完成输入。

给定 $M$ 和 $R$，请编写程序，求出 JOI 君所需执行的最少操作次数。

输入格式

输入通过标准输入以如下格式给出：

$M$ $R$

输出格式

输出一行，表示输入一个除以 $M$ 余数为 $R$ 的正整数所需的最少操作次数。

100000 13

5

4 3

3

提示

样例 1 解释

在此例中，通过以下 5 次操作可以输入数字 $13$：

• 将光标向上移动，此时光标指向数字 $1$ 的按键。
• 按下该键，输入数字 $1$。
• 将光标向右移动，此时光标指向数字 $2$ 的按键。
• 再次将光标向右移动，此时光标指向数字 $3$ 的按键。
• 按下该键，输入数字 $3$，此时已输入的数字序列为 $13$。

由于无法通过 4 次或更少的操作输入满足条件的整数，因此输出 $5$。

数据范围

• $2 \le M \le 100\,000$。
• $1 \le R < M$。
• 所有输入值均为整数。

子任务

1. （30 分）$M = 100\,000$。
2. （70 分）无额外限制。

翻译由 Qwen3-235B 完成