Số may mắn

View as PDF

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

Please read the guidelines before commenting.


There are no comments at the moment.