숫자 키패드

문제

JOI 군은 숫자 키패드를 $1$ 개 가지고 있다. 이 숫자 키패드에는 $0$ 부터 $9$ 까지의 숫자가 인쇄된 키가 아래 그림과 같이 배치되어 있다. $2$ 가 인쇄된 키의 아래, 그리고 $3$ 이 인쇄된 키의 아래에는 키가 존재하지 않음에 주의하시오.

또한 이 숫자 키패드에는, 숫자 키패드에 배치된 키 중 $1$ 개의 키를 가리키는 커서가 존재한다. 커서는 처음에 $0$ 이 인쇄된 키를 가리키고 있다.

JOI 군은 $1$ 번의 조작으로 다음 중 하나를 골라서 수행할 수 있다.

• 커서를, 현재 커서가 가리키고 있는 키와 상하좌우로 인접한 키로 이동시킨다. 단, 키가 존재하지 않는 위치로 커서를 이동시킬 수는 없다.
• 키를 누른다. 즉, 커서가 가리키고 있는 키에 인쇄된 숫자를 입력한다. 이때, 이전의 조작으로 이미 숫자가 입력되어 있었던 경우, 이미 입력되어 있던 숫자의 바로 오른쪽에 새로운 숫자가 입력된다.

지금, JOI 군은 이 숫자 키패드를 사용하여 $M$ 으로 나눈 나머지가 $R$ 인 양의 정수를 입력하고 싶다. 숫자 키패드의 조작에는 시간이 걸리므로, 가능한 한 적은 조작 횟수로 입력하고 싶다.

$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$ 줄에 출력한다.

예제 입력 1

100000 13

예제 출력 1

5

이 예제에서는, 다음 $5$ 번의 조작을 수행하여 $13$ 을 입력할 수 있다. $4$ 번 이하의 조작으로 조건을 만족하는 정수를 입력하는 것은 불가능하므로, $5$ 를 출력한다.

• 커서를 위로 이동시킨다. 커서가 가리키는 키는 $1$ 이 된다.
• 키를 누른다. $1$ 이 입력된다.
• 커서를 오른쪽으로 이동시킨다. 커서가 가리키는 키는 $2$ 가 된다.
• 커서를 오른쪽으로 이동시킨다. 커서가 가리키는 키는 $3$ 이 된다.
• 키를 누른다. $3$ 이 새로 입력되어, 지금까지 입력된 숫자는 $13$ 이 된다.

예제 입력 2

4 3

예제 출력 2

3

이 예제에서는, $3$ 번의 조작을 수행하여 $11$ 을 입력할 수 있다. $3$ 을 입력하려면 $4$ 번 이상의 조작을 수행해야 하므로, 최적이 아님에 주의하시오.