#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;
using namespace chrono;
typedef signed char i8;typedef short i16;typedef int i32;typedef long long i64;typedef unsigned char u8;typedef unsigned short u16;typedef unsigned u32;typedef unsigned long long u64;typedef float f32;typedef double f64;typedef long double f96;
template<typename A,typename B>void to_max(A& a,B b){if(a<b)a=b;}
template<typename A,typename B>void to_min(A& a,B b){if(b<a)a=b;}
#define __use_fast_io
namespace fast_io{
#ifndef __cplusplus
#define __cplusplus 201402L
#endif
const unsigned is(1<<21),os(1<<14);bool ne;char i[is],o[os],*ib(i),*ie(i),*ob(o),*oe(o+os),a[20],&c(*a),*b;void f(){ob-=fwrite(o,1,ob-o,stdout);}void p(char c){if(ob==oe)f();*ob++=c;}template<typename T>void _write(T&r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r;r/=10)*++b=(r%10)^'0';while(b!=a)p(*b--);}
#define g (ib==ie&&(ie=(ib=i)+fread(i,1,is,stdin),ib==ie)?-1:*ib++)
void reads(char*s){for(c=g;~c&&isspace(c);c=g);for(*s++=c,c=g;~c&&!isspace(c);c=g)*s++=c;*s=0;}template<typename T>void read(T&r){ne=false;for(c=g;~c&&(c<'0'||c>'9');c=g)ne=(c=='-');for(r=c^'0',c=g;isdigit(c);c=g)r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}template<>void read<char>(char&r){for(c=g;~c&&isspace(c);c=g);r=c;}template<>void read<string>(string&r){r.clear();for(c=g;~c&&isspace(c);c=g);for(r.push_back(c),c=g;~c&&!isspace(c);c=g)r.push_back(c);}
#undef g
#if(__cplusplus>=201703L)
template<typename...Args>void read(Args&...args){(read(args),...);}template<typename...Args>void _write(Args&...args){(_write(args),...);}
#else
template<typename T,typename...args>void read(T&a,args&...b){read(a);read(b...);}template<typename T,typename...args>void _write(T&a,args&...b){_write(a);_write(b...);}
#endif
template<>void _write<char>(char&r){p(r);}template<>void _write<char*>(char*&r){for(;*r;p(*r++));}template<>void _write<const char*>(const char*&r){for(;*r;p(*r++));}template<>void _write<string>(string&r){const char*s(r.data());_write(s);}template<typename...args>void write(args...a){_write(a...);}struct _des{~_des(){f();}}d;}using fast_io::read;using fast_io::reads;using fast_io::write;

constexpr int N(2e5+5);
char s[N];
int p,n,m,rem[N],li[N],unq_cnt,buc[N],block,pos[N];
i64 now_ans,ans[N];
struct inquiry{
	int l,r,i;
	bool operator<(const inquiry& other)const{
		return pos[l]==pos[other.l]?r>other.r:l>other.l;
	}
}inq[N];

int main(){
	int i,l,r;
	i64 pow_10(1);
	read(p);
	reads(s+1);
	n=strlen(s+1);
	block=sqrt(n);
	for(i=n;i;--i){
		rem[i]=(rem[i+1]+pow_10*(s[i]^'0'))%p;
		pow_10=pow_10*10%p;
	}
	memcpy(li+1,rem+1,n<<2);
	li[n+1]=0;
	sort(li+1,li+n+2);
	unq_cnt=unique(li+1,li+n+2)-li-1;
	for(i=1;i<=n;++i){
		pos[i]=(i<=block?1:pos[i-block]+1);
		rem[i]=lower_bound(li+1,li+unq_cnt+1,rem[i])-li;
	}
	read(m);
	for(i=1;i<=m;++i){
		read(inq[i].l,inq[i].r);
		inq[i].i=i;
	}
	sort(inq+1,inq+m+1);
	rem[n+1]=1;
	++buc[1];l=n+1;r=n;
	for(i=1;i<=m;++i){
		for(;l>inq[i].l;){
			--l;
			now_ans+=buc[rem[l]];
			++buc[rem[l]];
		}
		for(;r<inq[i].r;){
			++r;
			now_ans+=buc[rem[r+1]];
			++buc[rem[r+1]];
		}
		for(;r>inq[i].r;){
			--buc[rem[r+1]];
			now_ans-=buc[rem[r+1]];
			--r;
		}
		for(;l<inq[i].l;){
			--buc[rem[l]];
			now_ans-=buc[rem[l]];
			++l;
		}
		ans[inq[i].i]=now_ans;
	}
	for(i=1;i<=m;++i){
		write(ans[i],'\n');
	}
	return 0;
}