AC on # 6,7,8,17,19

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

int p,n,m,B,ans;
char str[200007];
int res[200007];
int a[200007],b[200007];
int c[200007];
struct query{
	int x,y,id;
}qu[200007];
bool cmp(query a,query b){
	if((a.x/B)!=(b.x/B)) return (a.x/B)>(b.x/B);
	return a.y<b.y;
}
bool t[10];
int nu[200007],ps[200007];
void work(){
	if(p==2) t[0]=t[2]=t[4]=t[6]=t[8]=1;
	if(p==5) t[0]=t[5]=1;
	for(int i=1;i<=n;i++){
		nu[i]=nu[i-1]+t[str[i]-'0'];
		ps[i]=ps[i-1]+t[str[i]-'0']*i;
	}
	scanf("%lld",&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",ps[y]-ps[x-1]-(nu[y]-nu[x-1])*(x-1));
	}
}
void del(int x){ c[x]--,ans-=c[x]; }
void add(int x){ ans+=c[x],c[x]++; }
signed main(){
	scanf("%lld%s",&p,str+1);
	n=strlen(str+1);
	if(p==2||p==5){
		work();
		return 0;
	}
	//printf("Yes\n");
	for(int i=1,pp=1;i<=n;i++){
		a[i]=(a[i-1]+(str[i]-'0')*pp%p)%p;
		b[i]=a[i];
		pp=(pp*10)%p;
	}
	sort(b+1,b+n+2);
	int ss=unique(b+1,b+n+2)-b-1;
	for(int i=0;i<=n;i++){
		a[i]=lower_bound(b+1,b+ss+1,a[i])-b;
		//printf("%lld\n",a[i]);
	}
	B=sqrt(n);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&qu[i].x,&qu[i].y);
		qu[i].x--,qu[i].id=i;
	}
	int l=1,r=0;
	sort(qu+1,qu+m+1,cmp);
	for(int i=1;i<=m;i++){
		while(l<=r+1&&l>qu[i].x) add(a[--l]);
		while(l<=r+1&&r<qu[i].y) add(a[++r]);
		while(l<=r+1&&l<qu[i].x) del(a[l++]);
		while(l<=r+1&&r>qu[i].y) del(a[r--]);
		res[qu[i].id]=ans;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",res[i]);
	return 0;
}