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~.