/*

  想了半天莫队，不知道咋转移，需要动下脑子。

  有一个很显然的结论是如果(l,r)是P的倍数，那么s[l...n]%P=s[r+1...n]%P。

  根据这个东西，我们预处理出所有的后缀%P的余数，接下里就是查询区间内相同得数对数量，就很好转移了。

  有一点，当P=2或5时，不否和上面的情况，需单独讨论。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<map>

#define N 200010

#define lon long long

using namespace std;

lon n,m,p,len,a[N],b[N],cnt[N],ans[N];char s[N];

map<lon,lon> mp;

struct node{

    lon l,r,id;

    bool operator<(node s1) const{

        if(l/len==s1.l/len) return r<s1.r;

        return l/len<s1.l/len;

    }

}q[N];

int main(){

    scanf("%lld%s%lld",&p,s+,&m);

    n=strlen(s+);len=(lon)sqrt(n);

    if(p!=&&p!=){

        lon bt=;

        for(lon i=n;i;i--){

            bt=bt*%p;

            a[i]=(a[i+]+(s[i]-'')*bt)%p;

            b[i]=a[i];

        }

        sort(b+,b+n+);

        for(lon i=;i<=n+;i++)

            mp[b[i]]=i;

        for(lon i=;i<=n+;i++)

            a[i]=mp[a[i]];

        for(lon i=;i<=m;i++){

            scanf("%lld%lld",&q[i].l,&q[i].r);

            q[i].id=i;q[i].r++;

        }

        sort(q+,q+m+);

        lon l=,r=,cur=;

        for(lon i=;i<=m;i++){

            while(r<q[i].r) ++r,cur+=cnt[a[r]]++;

            while(l>q[i].l) --l,cur+=cnt[a[l]]++;

            while(l<q[i].l) cur-=--cnt[a[l]],l++;

            while(r>q[i].r) cur-=--cnt[a[r]],r--;

            ans[q[i].id]=cur;

        }

        for(lon i=;i<=m;i++)

            printf("%lld\n",ans[i]);

    }

    else {

        for(lon i=;i<=n;i++)

            if(!((s[i]-'')%p))

                cnt[i]=cnt[i-]+,a[i]=a[i-]+i;

            else cnt[i]=cnt[i-],a[i]=a[i-];

        for(lon i=;i<=m;i++){

            lon l,r;

            scanf("%lld%lld",&l,&r);

            printf("%lld\n",a[r]-a[l-]-(cnt[r]-cnt[l-])*(l-));

        }

    }

    return ;

}

　　小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345
。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也
是P 的倍数）。例如 S为0077时，其子串 007有6个子串：0,0,7,00,07,007；显然0077的子串007有6个子串都是素
数7的倍数。

　　第一行一个整数：P。第二行一个串：S。第三行一个整数：M。接下来M行，每行两个整数 fr,to，表示对S 的
子串S[fr…to]的一次询问。注意：S的最左端的数字的位置序号为 1；例如S为213567，则S[1]为 2，S[1…3]为 2
13。N,M<=100000，P为素数

　　输出M行，每行一个整数，第 i行是第 i个询问的答案。