#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int p;

char s[N];

namespace BF1{

    LL s1[N], s2[N];

    void solve() {

        scanf("%s",s + );

        int n = strlen(s + );

        for (int i = ; i <= n; ++i) {

            s1[i] = s1[i - ], s2[i] = s2[i - ];

            if ((s[i] - '') % p == ) s1[i] ++, s2[i] += i;

        }

        int m = read();

        while (m --) {

            int l = read(), r = read();

            printf("%lld\n", s2[r] - s2[l - ] - 1ll * (l - ) * (s1[r] - s1[l - ]));

        }

    }

}

namespace BF2{

    struct Que{ int l, r, bel, id; } Q[N];

    bool operator < (const Que &A,const Que &B) { return A.bel == B.bel ? A.r < B.r : A.bel < B.bel; }

    int a[N], cnt[N];

    LL ans[N], b[N], disc[N];

    void solve() {

        scanf("%s", s + );

        int n = strlen(s + ), B = sqrt(n);

        for (int i = n, pw = ; i >= ; --i, pw = 1ll * pw *  % p) // 开long long

            disc[i] = b[i] = (1ll * (s[i] - '') * pw % p + b[i + ]) % p;

        disc[n + ] = ;

        sort(disc + , disc + n + );

        int tot = ;

        for (int i = ; i <= n + ; ++i) if (disc[i] != disc[tot]) disc[++tot] = disc[i];

        for (int i = ; i <= n + ; ++i) a[i] = lower_bound(disc + , disc + tot + , b[i]) - disc;

        int m = read();

        for (int i = ; i <= m; ++i)

            Q[i].l = read(), Q[i].r = read() + , Q[i].bel = (Q[i].l - ) / B + , Q[i].id = i;

        sort(Q + , Q + m + );

        int L = , R = ; LL now = ;

        for (int i = ; i <= m; ++i) {

            while (L > Q[i].l) L --, now += cnt[a[L]], cnt[a[L]] ++;

            while (R < Q[i].r) R ++, now += cnt[a[R]], cnt[a[R]] ++;

            while (L < Q[i].l) cnt[a[L]] --, now -= cnt[a[L]], L ++;

            while (R > Q[i].r) cnt[a[R]] --, now -= cnt[a[R]], R --;

            ans[Q[i].id] = now;

        }

        for (int i = ; i <= m; ++i) printf("%lld\n", ans[i]);

    }

}

int main() {

    p = read();

    if (p ==  || p == ) BF1::solve();

    else BF2::solve();

    return ;

}