#include<bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;

const int N=1e6+1e3+7;

int cnt[16][1<<16];

int n,m,B;

char S[N];

int a[N],s[N];

vector<int> pos[16];

int main()
{
    scanf("%d%d%d",&n,&m,&B);
    scanf("%s",S+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=islower(S[i])?S[i]-'a'+10:S[i]-'0';
        a[i]%=(B-1);
    }
    vector<pii>st;
    pos[0].push_back(0);
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+a[i])%(B-1);
        st.push_back({1<<a[i],i});
        for(auto &[x,y]:st)
            x|=1<<a[i];
        vector<pii> nst;
        for(auto [x,y]:st)
        {
            if(nst.empty()||x!=nst.back().first)
                nst.push_back({x,y});
        }
        st.swap(nst);
        for(int y=(int)st.size()-1;y>=0;y--)
        {
            int R=st[y].second,L=y>0?st[y-1].second+1:1;
            for(int j=0;j<B;j++)
            {
                int v=(s[i]-j+B-1)%(B-1);
                int A=upper_bound(pos[v].begin(),pos[v].end(),R-1)-lower_bound(pos[v].begin(),pos[v].end(),L-1);
                
                cnt[j][st[i].first]+=A;
            }
        }
    }
    int W=B-1;
    for(int i=0;i<W;i++)
        for(int S=0;S<(1<<W);S++)
            for(int i=0;i<W;i++)
                if(S>>i&1)
                    cnt[i][S^(1<<i)]+=cnt[i][S];
    while(m--)
    {
        scanf("%s",S);
        int x=islower(S[0])?S[0]-'a'+10:S[0]-'0';
        scanf("%s",S);
        int p=strlen(S);
        int E=0;
        for(int i=0;i<p;i++)
            E|=1<<(islower(S[i])?S[i]-'a'+10:S[i]-'0');
        if(E>>B&1)
            E|=1,E^=1<<B;
        long long ans=1ll*n*(n+1)/2;
        for(int j=0;j<W;j++)
        {
            int s=(x-j+W)%(W);
            int nS=E>>s|(E<<(W)>>s);
            nS^=(1<<W)-1;
            ans-=cnt[j][nS];
        }
        printf("%lld\n",ans);
    }
}