VOSLUCKY - Số may mắn
Giới hạn- Thời gian: 0.5s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một số nguyên X được gọi là số may mắn nếu ước nguyên tố của X chỉ có 2 và 5. Ví dụ các số 2, 10, 25... là các số may mắn, ngược lại các số 09, 69, 15, 24 không là số may mắn. Cho một xâu S có độ dài N, chỉ gồm các số từ 0 tới 9. Hãy tính số chuỗi con gồm các kí tự liên tiếp của S, tạo thành một số không có các chữ số 0 vô nghĩa ở đầu và chia hết cho một số may mắn X cho trước.
Input
Dòng 1: Số nguyên T, số test đề bài (1≤T≤10).
T bộ test tiếp theo có dạng:
Dòng 1: Gồm hai số nguyên X và N (2≤X≤10 3 , 1≤N≤10 6 ).
Dòng 2: Một xâu S có độ dài N.
Output
Gồm T dòng tương ứng với kết quả của từng bộ test.
Example
Input:1
2 3
108
Output:4
Giải thích: Có 4 chuỗi con thỏa mãn là : 10, 0, 8 và 108.
- Người up: only_love97