Giải bài trực tuyến

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³, 1≤N≤10⁶).

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.