ref
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll p, su[100005], sv[100005], ans[100005];
int n, m, uu, vv, ww, cnt[100005], blc, bel[100005];
char ss[100005];
struct Node{
int ll, rr, id;
}q[100005];
void qwq(){
for(int i=1; i<=n; i++){
su[i] = su[i-1];
sv[i] = sv[i-1];
if((ss[i]-'0')%p==0){
su[i] += i;
sv[i]++;
}
}
while(m--){
scanf("%d %d", &uu, &vv);
printf("%lld
", su[vv]-su[uu-1]-(uu-1)*(sv[vv]-sv[uu-1]));
}
}
bool cmp(Node x, Node y){
if(bel[x.ll]!=bel[y.ll]) return bel[x.ll]<bel[y.ll];
if(bel[x.ll]&1) return x.rr<y.rr;
else return x.rr>y.rr;
}
void pwp(){
ll t=1, now=0;
blc = sqrt(n+1);
for(int i=n; i; i--){
su[i] = (su[i+1] + (ss[i] - '0') * t) % p;
t = t * 10 % p;
sv[++ww] = su[i];
bel[i] = (i - 1) / blc + 1;
}
n++;
su[n+1] = 0;
sv[++ww] = 0;
sort(sv+1, sv+1+ww);
ww = unique(sv+1, sv+1+ww) - (sv + 1);
for(int i=1; i<=n; i++)
su[i] = lower_bound(sv+1, sv+1+ww, su[i]) - sv;
for(int i=1; i<=m; i++){
scanf("%d %d", &q[i].ll, &q[i].rr);
q[i].rr++;
q[i].id = i;
}
sort(q+1, q+1+m, cmp);
int l=q[1].ll, r=l-1;
for(int i=1; i<=m; i++){
while(l<q[i].ll){
cnt[su[l]]--;
now -= cnt[su[l]];
l++;
}
while(l>q[i].ll){
l--;
now += cnt[su[l]];
cnt[su[l]]++;
}
while(r<q[i].rr){
r++;
now += cnt[su[r]];
cnt[su[r]]++;
}
while(r>q[i].rr){
cnt[su[r]]--;
now -= cnt[su[r]];
r--;
}
ans[q[i].id] = now;
}
for(int i=1; i<=m; i++)
printf("%lld
", ans[i]);
}
int main(){
cin>>p;
scanf("%s", ss+1);
n = strlen(ss+1);
cin>>m;
if(p==2 || p==5) qwq();
else pwp();
return 0;
}