Các loại đồng xu

Ở ngôi làng Olympic thần tiên, người dân sống trong các nông trại rộng lớn giữa các ngọn núi. Họ dùng hệ thống tiền xu riêng và di chuyển bằng thảm bay. Vào một ngày hội đặc biệt của năm, Trưởng làng Triết tổ chức bán các nông trại và các thảm bay với mức giá ưu đãi cho người dân: mỗi nông trại có giá tiền là $N$ đồng và mỗi thảm bay có giá tiền là $M$ đồng, trong đó $N$ và $M$ là các số nguyên dương.

Hệ thống tiền có nhiều mệnh giá khác nhau là các số nguyên dương, mỗi mệnh giá có số lượng xu không giới hạn. Thú vị là với mỗi mệnh giá của hệ thống tiền ở đây, người dân có thể dùng một hoặc nhiều xu cùng loại để có được số tiền vừa đúng $N$ đồng, đủ mua một nông trại. Trưởng làng đã tính toán rằng không có mệnh giá nào khác với các xu có trong làng mà cũng có tính chất thú vị như nêu trên.

Yêu cầu: Hãy viết chương trình tính số lượng xu ít nhất (có thể cùng loại hoặc khác loại, với số lượng tùy ý) để đổi ra được đúng $M$ đồng, là số tiền vừa đủ mua được một cái thảm bay.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên dương $N$ và $M$ với $1\le N\le {10}^{10}$, $1\le M\le {10}^5$.

Dữ liệu ra

In ra một số nguyên là số lượng xu ít nhất cần sử dụng để có thể mua được một cái thảm bay.

Ràng buộc

• $1\le N\le {10}^{10}$.
• $1\le M\le {10}^5$.

Subtasks

• Subtask 1 ($50\%$ số điểm): $1\le N\le 100$, $1\le M\le 1000$.
• Subtask 2 ($50\%$ số điểm): $1\le N\le {10}^{10}$, $1\le M\le {10}^5$.

Ví dụ