// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 1100005
#define inf 0x3f3f3f3f

int toint(char c){
	if(isdigit(c))return c&15;
	return c-'a'+10;
}

int n,m,k;
char s[maxn];
int a[maxn],aa[maxn];
signed sum[maxn][19];

int pre[20],id[20];
pii tmp[20];

int ask(int x,int l,int r){
	int res=sum[r][x];
	if(l>0)res-=sum[l-1][x];
	return res;
}

int f[18][1<<18];
void fwt(int*f,int k){
	For(i,0,k-1)
		For(j,0,(1<<k)-1)
			if(j>>i&1) f[j]+=f[j^(1<<i)];
}

int res0,res1[19],res10[19];
int L[maxn],R[maxn];

signed main()
{
	n=read(),m=read(),k=read(),cin>>(s+1);
	sum[0][0]=1;
	For(i,1,n){
		a[i]=a[i-1]+toint(s[i]),a[i]%=(k-1);
		aa[i]=aa[i-1]+(toint(s[i])!=0);
		res10[toint(s[i])]++;
		For(j,0,k-2)sum[i][j]=sum[i-1][j]+(j==a[i]);
	}
	memset(pre,-1,sizeof pre);
	For(j,0,k) id[j]=j;
	
	For(i,1,n){
		pre[toint(s[i])%(k-1)]=i;
		sort(id,id+k-1,[&](int x,int y){
			return pre[x]>pre[y];
		});
		int S=0;
		For(j,0,k-2){
			int r=pre[id[j]];
			int l=pre[id[j+1]]+1;
			l=max(l,1ll);
			S|=(1<<id[j]);
			if(l>r)continue;
		//	cout<<"i,l,r, "<<i<<" "<<l<<" "<<r<<" "<<S<<"\n";
			For(x,0,k-2)
				f[(a[i]-x+k-1)%(k-1)][S]+=ask(x,l-1,r-1);
		}
	}
	
	int nows=1;
	For(i,1,n){
		if(aa[i]!=aa[i-1]) nows=0;
		res0+=nows,++nows;
	}
	
	For(i,1,n){
		L[i]=L[i-1];
		if(toint(s[i])!=0) L[i]=i;
	}
	R[n+1]=n+1;
	Rep(i,n,1){
		R[i]=R[i+1];
		if(toint(s[i])!=0) R[i]=i;
	}
	
	For(i,1,n) if(toint(s[i])!=0) {
		int x=toint(s[i]);
		int l=L[i-1],r=R[i+1];
		res1[x]+=(i-l)*(r-i);
	}
	
//	For(i,1,n)For(j,i,n){
//		int S=0,T=0;
//		For(p,i,j)S|=(1<<(toint(s[p])%(k-1))),T|=(1<<toint(s[p]));
//	//	cout<<(a[j]-a[i-1]+k-1)%(k-1)<<" "<<S<<"\n";
//		if(aa[j]-aa[i-1]==1){
//			int x=0;
//			For(_,1,k-1) if(T>>_&1) x=_;
//			res1[x]++;
//		}
//	}
	
	For(x,0,k-2) fwt(f[x],k-1);
	
	//if(m==22517)m=20000;
	For(_,1,m){
		char yy;
		cin>>yy;
		int y=toint(yy);
		string str; cin>>str;
		
		int S=0;
		for(auto c:str){
			int o=toint(c);
			S|=(1<<(o%(k-1)));
		}
		int res=n*(n+1)/2;
		For(x,0,k-2)if(x!=y%(k-1)){
			// if have j,x-i+j==y
			// j==y+i-x
			// 
			int d=(y-x+k-1)%(k-1);
			int T=0;
			T|=(S>>d);
			T|=(S<<(k-1-d));
			T&=(1<<(k-1))-1;
	//		cout<<"T "<<T<<"\n";
			T^=(1<<(k-1))-1;
		//	cout<<T<<" "<<TT<<"\n";
		//	cout<<"x,T "<<x<<' '<<T<<" "<<f[x][T]<<"\n";
			res-=f[x][T];
		}
		if(y==0||y==k-1){
			if(y==0){
				res=res0;
				bool fl0=0;
				for(auto c:str) if(toint(c)==0) fl0=1;
				if(fl0){
					For(j,1,k-1) res+=res1[j];
				}
			}else{
			//	cout<<"ans "<<res<<"\n";
				bool fl=0,fl0=0;
				for(auto c:str){
					if(toint(c)==k-1)fl=1;
					if(toint(c)==0)fl0=1;
				}
				if(!fl){
					res-=res0;
				//	cout<<"QWQ "<<res<<"\n";
					if(fl0){
						For(j,1,k-2) {
							int s1=res10[j];
							int s2=res1[j]-s1;
							res-=s1;
							if(!(S>>(k-1-j)&1)) res-=s2;
						}
					}
				}
			}
		}
		cout<<res<<"\n";
	}
    return 0;
}
/*
5 10 5
01234
0 1

01234

*/