考虑一个区间$[l,r]$,记$a_i=s[l\sim n]$,产生贡献的条件是$\frac{a_l-a_{r+1}}{10^{n-r}}\text{mod}~ p=0 $

即$\frac{a_l-a_{r+1}}{10^{n-r}}\equiv 0(\text{mod}~p)$

那么就要分情况讨论了,

$p$不是$2,5$时,即不是$10$的质因子,

有:$a_l\equiv a_{r+1}(\text {mod} ~p)$

因此一个询问变成了$[l,r+1]$中符合$a$值相等的对数。

套用一下莫队就可以解决了。

当$p$是$2,5$时,直接判断末尾就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll p;char str[N];int n,m;
namespace task1
{
    int s1[N];ll s2[N];
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            s1[i]=s1[i-1];s2[i]=s2[i-1];
            if((str[i]^48)%p==0)++s1[i],s2[i]+=i;
        }
        for(int i=1,l,r;i<=m;i++)
        {
            qr(l);qr(r);
            qw(s2[r]-s2[l-1]-1ll*(l-1)*(s1[r]-s1[l-1]));puts("");
            //s2[r]-s2[l-1]是末尾不在[l,r]的,(l-1)*(s1[r]-s1[l-1])是末尾合法,但起点 不合法的。 
        }
    }
}
namespace task2
{
    int bel[N],len,cnt[N];ll arr[N],a[N],Ans[N];
    struct Query{int id,l,r;}Q[M];
    inline bool cmp(Query a,Query b){return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];}
    inline int get(ll d)
    {
        int l=1,r=len;
        while(l<r)
        {
            int mid=l+r>>1;
            if(arr[mid]<d)l=mid+1;
            else r=mid;
        }
        return l;
    }
    void solve()
    {
        int sqr=sqrt(n),T=(n-1)/sqr+1;
        for(int i=1,L=1,R=sqr;i<=T;i++,L=R+1,R=L+sqr-1)
            for(int j=L;j<=R;j++)bel[j]=i;
        ll t=1;
        for(int i=n;i;i--,t=t*10%p)
            arr[i]=a[i]=(a[i+1]+(str[i]^48)*t)%p;
        arr[n+1]=0;len=n+1;sort(arr+1,arr+len+1);len=0;
        for(int i=1;i<=n+1;i++)
            if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
        for(int i=1;i<=n+1;i++)a[i]=get(a[i]);
        for(int i=1;i<=m;i++)Q[i].id=i,qr(Q[i].l),qr(Q[i].r),++Q[i].r;
        sort(Q+1,Q+m+1,cmp);ll ans=0;int l=1,r=0;
        for(int i=1;i<=m;i++)
        {
            while(r<Q[i].r)ans+=cnt[a[++r]]++;
            while(l>Q[i].l)ans+=cnt[a[--l]]++;
            while(r>Q[i].r)ans-=--cnt[a[r--]];
            while(l<Q[i].l)ans-=--cnt[a[l++]];
            Ans[Q[i].id]=ans;
        }
        for(int i=1;i<=m;i++)qw(Ans[i]),puts("");
    }
}
int main()
{
//    freopen("number2.in","r",stdin);
//    freopen("number2.ans","w",stdout);
    qr(p);scanf("%s",str+1);n=strlen(str+1);qr(m);
    if(p==2||p==5)task1::solve();
    else task2::solve();
    return 0;
}