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

#define int long long

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 dp[N][2],F[2];

int g[N][2],G[2];

signed main()
{
    scanf("%lld%lld%lld",&n,&m,&B);
    scanf("%s",S+1);
    int cz=0,sz=0,nz=0,bz=0;
    for(int i=1;i<=n;i++)
    {
        if(S[i]=='0')
        {
            for(int j=0;j<2;j++)
                dp[i][j]=dp[i-1][j];
        }
        else
        {
            dp[i][1]=dp[i-1][0];
        }
        dp[i][S[i]!='0']++;
        for(int j=0;j<2;j++)
            F[j]+=dp[i][j];


        if(S[i]=='0')
            sz++;
        else
            sz=0;
        cz+=sz;
        a[i]=islower(S[i])?S[i]-'a'+10:S[i]-'0';
        bz+=a[i]==B-1;
        a[i]%=(B-1);

        
            
        if(a[i]==0)
        {
            for(int j=0;j<2;j++)
                g[i][j]=g[i-1][j];
        }
        else
        {
            g[i][1]=g[i-1][0];
        }
        g[i][a[i]!=0]++;
        for(int j=0;j<2;j++)
            G[j]+=g[i][j];
        nz+=S[i]!='0';
    }
    vector<pii>st;
    pos[0].push_back(0);
    int W=B-1;
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+a[i])%W;
        pos[s[i]].push_back(i);
        st.push_back({1<<a[i],i});
        for(auto &[x,y]:st)
            x|=1<<a[i];
        vector<pii> nst;
        reverse(st.begin(),st.end());
        for(auto [x,y]:st)
        {
            if(nst.empty()||x!=nst.back().first)
                nst.push_back({x,y});
        }
        st.swap(nst);
        reverse(st.begin(),st.end());
        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<W;j++)
            {
                int v=(s[i]-j+W)%(W);
                int A=upper_bound(pos[v].begin(),pos[v].end(),R-1)-lower_bound(pos[v].begin(),pos[v].end(),L-1);
                // if(j==2&&A)n
                cnt[j][st[y].first]+=A;
            }
        }
    }
    for(int t=0;t<W;t++)
        for(int i=0;i<W;i++)
            for(int S=0;S<(1<<W);S++)
                if(!(S>>i&1))
                    cnt[t][S^(1<<i)]+=cnt[t][S];
    while(m--)
    {
        scanf("%s",S);
        int x=islower(S[0])?S[0]-'a'+10:S[0]-'0';
        int bx=x;
        x%=W;
        scanf("%s",S);
        if(bx==0)
        {
            int p=strlen(S);
            bool ok=0;
            for(int j=0;j<p;j++)
                if(S[j]=='0')
                    ok=1;
            printf("%lld\n",F[0]+ok*(F[1]));
            continue;
        }
        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');
        long long ans=0;
        if(x==0)
            ans-=cz;
        ans+=cnt[x][(1<<W)-1];
        if(E&(1<<W))
        {
            E^=(1<<W);
            E|=1;
        }
        else if((E&1)&&!(E&(1<<W)))
        {
            if(x==0)
                ans-=G[1];
        }
        for(int j=0;j<W;j++)
        {
            if(j==x)
                continue;
            int s=(x-j+W)%(W);
            int nS=E>>s|((E<<(W)>>s)&((1<<W)-1));
            nS^=(1<<W)-1;
            ans+=cnt[j][(1<<W)-1]-cnt[j][nS];
        }
        printf("%lld\n",ans);
    }
}