Submit solution
Points:
1.60 (partial)
Time limit:
0.75s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
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 \leq T \leq 10)~.
~T~ bộ test tiếp theo có dạng:
- Dòng ~1~: Gồm hai số nguyên ~X~ và ~N~ ~(2 \leq X \leq 10^{3}~, ~1 \leq N \leq 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.
Sample Input
1
2 3
108
Sample Output
4
Note
Có ~4~ chuỗi con thỏa mãn là: ~10~, ~0~, ~8~ và ~108~.
Comments