问题描述

JOI 君有一个数字键盘。这个数字键盘上标有从 $0$ 到 $9$ 的数字键，如下图所示。请注意，位于标有 $2$ 和 $3$ 的键下方没有键。

此外，这个数字键盘上有一个光标，指示其中一个键。光标最初指向标有 $0$ 的键。

JOI 君可以在一次操作中选择以下操作之一：

• 将光标移动到当前光标指向的键的上下左右相邻键。但是，不能将光标移动到不存在的位置。
• 按下键。也就是说，输入标有光标指向键上的数字。在此操作之前，如果已经通过之前的操作输入了数字，则新输入的数字将紧跟在之前输入的数字右侧。

现在，JOI 君希望使用这个数字键盘输入一个正整数，使得该整数除以 $M$ 的余数为 $R$。由于操作数字键盘需要时间，JOI 君希望尽量少地进行操作。

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

约束条件

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

子任务

1. ($30$ 分) $M = 100,000$。
2. ($70$ 分) 没有额外限制。

输入

输入从标准输入读取，具有以下格式。

$M$ $R$

输出

为了使得输入的正整数除以 $M$ 的余数为 $R$，请输出所需的最少操作次数。

输入示例 1

100000 13

输出示例 1

5

在此示例中，可以通过执行以下 $5$ 次操作来输入 $13$。无法通过 $4$ 次或更少的操作来输入满足条件的整数，因此输出为 $5$。

• 将光标向上移动。光标指向 $1$。
• 按下键。输入 $1$。
• 将光标向右移动。光标指向 $2$。
• 将光标向右移动。光标指向 $3$。
• 按下键。新输入 $3$，之前输入的数字为 $13$。

输入示例 2

4 3

输出示例 2

3

在此示例中，可以通过执行 $3$ 次操作来输入 $11$。要输入 $3$，至少需要执行 $4$ 次操作，但请注意这不是最优的解。