Cho trước một số nguyên dương \(P\) không chia hết cho 2 và 5. Số \(X\) được gọi là một bội đặc biệt của \(P\) nếu số \(X\) chia hết cho \(P\) và \(X\) chỉ chứa toàn chữ số 9.

Ví dụ: Với \(P=7\) thì \(X=999999\) là một bội đặc biệt của số \(P\).

Yêu cầu: Cho trước hai số nguyên dương \(P\) và \(N\). Hỏi có bao nhiêu số \(X\) là bội đặc biệt của \(P\) và \(X\) có số chữ số không vượt quá \(N\).

Input

• Đọc từ file văn bản BOI.INP hai số \(P\) và \(N\) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

• Ghi ra file văn bản BOI.OUT số \(m\) là số lượng các số \(X\) thỏa mãn yêu cầu.

Example

7 7

1

Scoring

• 30% test tương ứng với \(P < 10^2\) và \(N \le 10^9\).
• 40% test tương ứng với \(10^2 \le P < 10^4\) và \(N \le 160\).
• 30% test tương ứng với \(10^4 \le P < 10^6\) và \(N \le 10^{18}\).