// 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 200005
#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],sum[maxn][17];
int pre[17],id[17];
pii tmp[17];
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[17][1<<17];
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 pre[maxn],nxt[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){
pre[i]=pre[i-1];
if(toint(s[i])!=0) pre[i]=i;
}
nxt[n+1]=n+1;
Rep(i,n,1){
nxt[i]=nxt[i+1];
if(toint(s[i])!=0) nxt[i]=i;
}
For(i,1,n) if(toint(s[i])!=0) {
int x=toint(s[i]);
int l=pre[i-1],r=nxt[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);
For(_,1,m){
int y=read();
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 T=0;
For(i,0,k-2){
// cout<<(((y+i-x+k-1)%(k-1)))<<"\n";
if(!(S>>((y+i-x+k-1)%(k-1))&1)) T|=(1<<i);
}
// 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
*/