Cho hai số nguyên \(n\) và \(k\). Hãy tìm số lượng số được tách từ \(n\) sao cho các số được tách từ \(n\) chia hết cho \(k\) và số lượng số tách được là lớn nhất (các số khi tách phải liên tiếp với nhau).

Ví dụ \(n = 12345\) và \(k = 3\) có những cách tách là {12; 3; 45} hoặc {12; 345} trong khi cách tách số không thỏa mãn là {1245; 3}.

Yêu cầu: In ra số lượng số lớn nhất tìm được.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) (\(n \le 10^{1000}\)).
• Dòng thứ hai gồm một số nguyên dương \(k\) (\(k \le 9\)).

Output

• In ra kết quả của bài toán, nếu không có kết quả thỏa mãn in ra \(0\).

Example

12345
3

3

433
2

0

2222
2

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(k\) là ước nguyên tố của \(10\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^8\).
• Subtask \(4\) (\(20\%\) số điểm): Không có giới hạn gì thêm.