#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    int n, q;
    string s;

    cin >> n >> q;
    cin >> s;

    vector<string> S(q);
    vector<int> A(q);   
    vector<int> C(q);

    for (int i = 0; i < q; i++){
        cin >> A[i] >> S[i];
    }

    for (int i = 0; i < q; i++){
        C[i] = 0;

        for (int start = 0; start < n; start++){
            if (s[start] == '0') {continue;}
            bool ok = true;
            int j = 0;
            int skipped = 0;

            for (int k = start; k < start + A[i] + skipped; k++){
                if (k >= n){
                    ok = false;
                    break;
                }

                //cout << k << " - " << s[k] << "//" << j << " - " << S[i][j] << endl;

                if (s[k] == '0'){
                    skipped++;
                    continue;
                }

                if (s[k] != S[i][j]){
                    ok = false;
                    break;
                }

                j++;
            }

            //cout << ok << endl;
            if (ok == true) {
                C[i]++;

                for (int j = start; j < start + A[i]; j++){
                    s[j] = '0';
                }
            }

            //cout << start << " - "<< s << endl;
        }
        
    }

    for (int i = 0; i < q; i++) {
        cout << C[i] << endl;
    }

    return 0;
}