004 - テンキー (Tenkey)

問題文

JOI 君はテンキーを 1 つ持っている．このテンキーには 0 から 9 までの数字が印字されているキーが以下の図のように配置されている． 2 が印字されたキーの下，および 3 が印字されたキーの下にはキーは存在しないことに注意せよ．

またこのテンキーには，テンキーに配置されているキーのうち 1 つのキーを指し示すカーソルが存在している．カーソルは最初 0 が印字されているキーを指し示している．

JOI 君は 1 回の操作で次のうちのいずれかを選んで行うことができる：

• カーソルを，現在カーソルが指し示しているキーと上下左右に隣接しているキーに移動させる．ただし，キーが存在しない場所にカーソルを移動させることはできない．
• キーを押す．すなわち，カーソルが指し示しているキーに印字されている数字を入力する．この際，以前の操作によってすでに数字が入力されていた場合，すでに入力されていた数字のすぐ右に新たな数字が入力される．

いま，JOI 君はこのテンキーを使って， M で割った余りが R であるような正の整数を入力したいと考えている．テンキーの操作には時間がかかるので，なるべく少ない操作回数で入力したい．

M と R が与えられるので，JOI 君が行う必要のある操作の回数の最小値を求めるプログラムを作成せよ．

制約

• 2 ≤ M ≤ 100,000．
• 1 ≤ R < M．
• 入力される値はすべて整数である．

小課題

1. (30 点) M = 100,000．
2. (70 点) 追加の制限はない．

入力

入力は以下の形式で標準入力から与えられる．

M R

出力

M で割った余りが R であるような正の整数を入力するために必要な操作の回数の最小値を 1 行で出力せよ．

入力例 1

100000 13

出力例 1

5

この例では，以下の 5 回の操作を行うことによって 13 を入力することが可能である． 4 回以下の操作によって条件を満たす整数を入力することは不可能であるので， 5 を出力する．

• カーソルを上に移動させる．カーソルが指し示すキーは 1 となる．
• キーを押す． 1 が入力される．
• カーソルを右に移動させる．カーソルが指し示すキーは 2 となる．
• カーソルを右に移動させる．カーソルが指し示すキーは 3 となる．
• キーを押す． 3 が新たに入力され，これまでに入力された数字は 13 となる．

入力例 2

4 3

出力例 2

3

この例では，3 回の操作を行うことによって 11 を入力することが可能である．3 を入力するには 4 回以上の操作を行わなければならず，最適ではないことに注意せよ．