//Yên Bái 2014

Rubick là một bậc thầy về ma thuật, hắn ta có thể bắt chước tất cả mọi tuyệt chiêu trên đời. Sở dĩ hắn làm được như vậy là nhờ khả năng quan sát dấu vết để lại khi đối thủ tung đòn ma thuật và hắn luôn nhớ lời dạy của sư phụ mình rằng: “những trận chiến luôn để lại một chuỗi số, trong đó những số cùng độ dài L và chia hết cho một số X sẽ là dấu vết của cùng một chiêu thức.”

Ta không thể làm như Rubick, nhưng dựa vào điều trên ta có thể biết được một tuyệt chiêu đã được sử dụng bao nhiêu lần dựa vào chuỗi số, độ dài L và số X.

Yêu cầu: Hãy xác định số lần tuyệt chiêu được tìm thấy.

Dữ liệu: Vào từ file văn bản DIVISION.INP gồm nhiều dòng:

• Dòng  thứ nhất: số nguyên dương T – số lượng test
• Các dòng sau là T bộ dữ liệu, mỗi  bộ gồm 2 dòng :
  • Dòng 1: 2 số nguyên dương X và L;
  • Dòng 2: chuỗi số;  

Kết quả:

Gồm T dòng, mỗi dòng là số lần tuyệt chiêu được tìm thấy trong mỗi bộ test

Giải thích 

Bộ  1 Có số 1302 là chia hết cho 3, số 0252 chia hết cho 3 nhưng chỉ có 3 chữ số, không được tính.

Bộ 2 Gồm 3 số 1234, 2348, 4876;

Giới hạn :

Testcase 1 (2 test): dài chuỗi ≤ 200; L ≤ 8.

Testcase 2 (2 test): độ dài chuỗi ≤ 1000; L ≤ 16.

Testcase 3 (2 test): độ dài chuỗi ≤ 1000; L ≤ 50.

Testcase 4 (1 test): độ dài chuỗi ≤ 100000; L ≤ 1000.

Tất cả các test đều có T ≤ 10