#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i =a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fo(i, n) rep(i, 0, n)
#define F first
#define S second
#define MP make_pair
#define PB push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<vector<ll>> vvll;

map<string, set<int>> ds;
const int NMAX = 112345;
const int qm=5;

int prevch[NMAX];
int nextch[NMAX];
bool exis[NMAX];
char in[NMAX];

void modify_from(int start, bool remove)
{
	if(start==0) return;
	int pl = start;
	char x[20];
	for(int i=0;i<5;i++)
	{
		x[i] = in[pl];
		x[i+1] = 0;
		pl = nextch[pl];
		if(remove)
			ds[x].erase(start);
		else
			ds[x].insert(start);
	}

}
void remove_at(int p)
{
	int pl = p;
	fo(i,5)
	{
		modify_from(pl, true);
		pl = prevch[pl];
	}

	prevch[nextch[p]] = prevch[p];
	nextch[prevch[p]] = nextch[p];
	exis[p]=0;

	pl = p;
	fo(i,4)
	{
		pl = prevch[pl];
		modify_from(pl, false);
	}
}

signed main() {
	int n,q;
	scanf("%d%d %s", &n, &q, in+1);
	n+=2;
	in[0] = '_';
	in[n-1] = '_';
	fo(i,10) in[n+i]='_';

	fo(i,n) prevch[i] = i?i-1:0;
	fo(i,n) nextch[i] = i==n-1?i:i+1;
	fo(i,n) exis[i] = 1;

	fo(i,n)
	{
		char x[10];
		fo(j, qm)
		{
			x[j] = in[i+j];
			x[j+1]=0;
			ds[x].insert(i);
		}
	}

	fo(i,q)
	{
		int ql;
		char s[10];
		scanf("%d %s", &ql, s);
		int out = 0;

		set<int> cp = ds[s];
		for(int start: cp) if(exis[start])
		{
			out ++;
			int pl = start;
			fo(_, ql)
			{
				remove_at(pl);
				pl = nextch[pl];
			}
		}

		printf("%d\n", out);

	}
}