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

#define int long long

using pii=pair<int,int>;

const int N=1e6+1e5+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];

signed g[N][2][16][2];

int G[2][16][2];

int pre[N][16];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // scanf("%lld%lld%lld",&n,&m,&B);
    cin>>n>>m>>B;
    // n=m=1<<20;
    // B=16;
    // scanf("%s",S+1);
    cin>>(S+1);
    // for(int i=1;i<=n;i++)
    //     S[i]='0'+rand()%10;
    // return 0;
    int cz=0,sz=0,nz=0,bz=0;
    int W=B-1;
    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(S[i]=='0')
        {
            for(int j=0;j<2;j++)
                for(int k=0;k<W;k++)
                    g[i][j][(k+a[i])%W][1]=g[i-1][j][k][0]+g[i-1][j][k][1];
        }
        else if(a[i]!=0)
        {
            for(int j=0;j<W;j++)
                g[i][1][(j+a[i])%W][1]=g[i-1][0][j][0]+g[i-1][0][j][1];
        }
        if(S[i]=='0'||a[i]!=0)
            g[i][a[i]!=0][a[i]][0]++;
        for(int j=0;j<2;j++)
            for(int k=0;k<W;k++)
                for(int t=0;t<2;t++)
                G[j][k][t]+=g[i][j][k][t];
        nz+=S[i]!='0';
    }
    vector<pii>st;
    pos[0].push_back(0);
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+a[i])%W;
        for(int j=0;j<W;j++)
            pre[i][j]=pre[i-1][j]+(s[i]==j);
        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
                int A=pre[R][v]-pre[L-1][v];
                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--)
    {
        cin>>S;
        S[0]='1',S[1]=0;
        int x=islower(S[0])?S[0]-'a'+10:S[0]-'0';
        int bx=x;
        x%=W;
        cin>>S;
        S[0]='2';
        if(bx==0)
        {
            int p=strlen(S);
            bool ok=0;
            for(int j=0;j<p;j++)
                if(S[j]=='0')
                    ok=1;
            cout<<F[0]+ok*F[1]<<"\n";
            // 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;
            ans+=cnt[x][(1<<W)-1];
        if(x==0&&!(E&(1<<W)))
            ans-=F[0];
        if(E&(1<<W))
        {
            E^=(1<<W);
            E|=1;
        }
        else if((E&1))
        {
            if(x==0)
            {
                for(int t=0;t<W;t++)
                {
                    if(!(E>>t&1))
                    {
                        // assert(!G[1][0][1]);
                        ans-=G[1][(W-t)%W][1];
                    }
                    ans-=G[1][t][0];
                }
            }
        }
        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];
        }
        cout<<ans<<"\n";
    }
}