RT

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define int long long
using namespace std;
const int N=200010;
struct qwe{
	int l,r,id;
}q[N];

int mod,n,m,k,g;
int l=1,r=0,ql,qr,qi;

char a[N<<3];
int cnt[N],anss[N];
int ans;
int sum[N],b[N];

bool cmp(qwe x,qwe y)
{
	if(x.r/g==y.r/g)return x.l<y.l;
	return x.r<y.r;
}

void add(int x)
{
	ans+=cnt[sum[x]];
	cnt[sum[x]]++;
}

void del(int x)
{
	cnt[sum[x]]--;
	ans-=cnt[sum[x]];
}

signed main()
{
	scanf("%lld",&mod);

	cin>>a+1;
	a[0]=' ';
	n=strlen(a+1);
	g=sqrt(n);
	int mi=1;
	for(int i=n;i>=1;i--)
	{
		sum[i]=b[i]=(b[i+1]+mi*(a[i]-'0')%mod)%mod;
		mi=mi*10%mod;
	}
	sum[++n]=0;
	int tot=n;
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	for(int i=1;i<=n;i++)
		sum[i]=lower_bound(b+1,b+1+tot,sum[i])-b;
	
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	
	for(int i=1;i<=m;i++)
	{
		ql=q[i].l,qr=q[i].r+1,qi=q[i].id;
		//cout<<ql<<" "<<qr<<endl;
		while(l<ql)del(l++);
		while(l>ql)add(--l);
		//cout<<ans<<endl;
		while(r<qr)add(++r);
		while(r>qr)del(r--);
		anss[qi]=ans;
	}	
	for(int i=1;i<=m;i++)printf("%lld\n",anss[i]);
}