JOI có một bàn phím số với các phím mang chữ số từ \(0\) đến \(9\), được bố trí như hình dưới đây. Lưu ý rằng không có phím nào ở ngay dưới phím \(2\) hoặc phím \(3\).

Trên bàn phím có một con trỏ chỉ vào một phím. Ban đầu con trỏ chỉ vào phím \(0\).

Trong mỗi thao tác, JOI có thể chọn một trong hai việc sau:

• Di chuyển con trỏ sang một phím kề với phím hiện tại theo hướng lên, xuống, trái hoặc phải. Không được di chuyển đến vị trí không có phím.
• Nhấn phím mà con trỏ đang chỉ vào để nhập chữ số trên phím đó. Nếu trước đó đã nhập các chữ số, chữ số mới được thêm ngay bên phải dãy chữ số đã nhập.

JOI muốn dùng bàn phím này để nhập một số nguyên dương có số dư bằng \(R\) khi chia cho \(M\). Vì thao tác trên bàn phím mất thời gian, JOI muốn dùng ít thao tác nhất có thể.

Cho \(M\) và \(R\), hãy tìm số thao tác ít nhất JOI cần thực hiện.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn gồm một dòng chứa hai số nguyên \(M\) và \(R\).

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất để nhập một số nguyên dương có số dư bằng \(R\) khi chia cho \(M\).

Ràng buộc

• \(2 \le M \le 100\,000\).
• \(1 \le R < M\).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. (30 điểm) \(M=100\,000\).
2. (70 điểm) Không có ràng buộc bổ sung.

Ví dụ

100000 13

5

4 3

3

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.