#pragma GCC optimize("O3, unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 55;
const int sigma = 2;
struct AhoCorasick
{
    AhoCorasick *trie[sigma] = {}, *prev = NULL;
    int cur = 0;


}*frev = new AhoCorasick, *location[10005], *coada[1000005];

AhoCorasick *inser(const char sir[])
{
    AhoCorasick *nod = frev;
    for(int i = 0; sir[i]; nod = nod->trie[sir[i++] - '0'])
    {
        if(!nod->trie[sir[i] - '0'])
            nod->trie[sir[i] - '0'] = new AhoCorasick;
    }
    return nod;
}
void solve(const char sir[])
{
    int st = 1, dr = 0;
    frev->prev = frev;
    for(coada[++dr] = frev; st <= dr; st++)
    {
        AhoCorasick *nod = coada[st];
        for(int i = 0; i < sigma; ++i)
        {
            if(nod->trie[i])
            {
                AhoCorasick * noddoi = nod->trie[i];
                AhoCorasick *copie = nod->prev;
                while(copie != frev && !copie->trie[i])
                    copie = copie->prev;
                if(copie->trie[i] && copie->trie[i] != noddoi)
                    noddoi->prev = copie->trie[i];
                else
                    noddoi->prev = copie;
                coada[++dr] = noddoi;
            }
        }
    }
    AhoCorasick *nod = frev;
    for(int i = 0; sir[i]; ++i)
    {
        while(nod != frev && !nod->trie[sir[i] - '0'])
            nod = nod->prev;
        if(nod->trie[sir[i] - '0'])
            nod = nod->trie[sir[i] - '0'];
        nod->cur++;
    }
    for(int   i = dr; i > 0; --i)
        if(coada[i]->prev)
        coada[i]->prev->cur += coada[i]->cur;
}




int tests;
 char sir[100005];
ifstream fin("virus.in");
ofstream fout("virus.out");
int32_t main(int argc, char * argv[])
{
    int lung;
    fin >> lung >> tests;
    fin >> sir;
    for(int i = 1; i <= tests; ++i)
    {
        char st[10005];
        int val;
        fin >> val >> st;
        location[i] =inser(st);
    }
    solve(sir);
    for(int i = 1; i <= tests; ++i)
        fout << location[i]->cur << '\n';
    return 0;
}