#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

const int N = (int)5e4 + 100;
const int K = 10;
const int LOG = 16;

int n;
char s[N];
int a[N];
int lst[K];

struct state {
    int len, link, cnt;
    map<int,int> next;
};

state st[N*2*11];
int sz, last;
int deg[N*2*11];
int sa_pos[N];
int orig_pos[N];
int sparse[LOG][N*2*11];

void sa_init() {
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
}

void sa_extend (int from, int to) {
    for (int i = from; i <= to; i++) {
        int c = a[i];
        if (st[last].next.count(c)) {
            last = st[last].next[c];
        }
        else {
            int cur = sz++;
            st[cur].len = st[last].len + 1;
            int p;
            for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
                st[p].next[c] = cur;
            if (p == -1)
                st[cur].link = 0;
            else {
                int q = st[p].next[c];
                if (st[p].len + 1 == st[q].len)
                    st[cur].link = q;
                else {
                    int clone = sz++;
                    st[clone].len = st[p].len + 1;
                    st[clone].next = st[q].next;
                    st[clone].link = st[q].link;
                    for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                        st[p].next[c] = clone;
                    st[q].link = st[cur].link = clone;
                }
            }
            last = cur;
        }
        sa_pos[i] = last;
    }
}

void solve()
{
    sa_init();
    for (int i = 0; i < K; i++)
        lst[i] = -1;
    for (int i = 0; i < n; i++)
    {
        if (lst[a[i]] != -1) {
            a[lst[a[i]]] = i - lst[a[i]] + 1;
            last = (lst[a[i]] == 0 ? 0 : sa_pos[lst[a[i]] - 1]);
            sa_extend(lst[a[i]], i-1);
        }
        lst[a[i]] = i;
        a[i] = 1;
        sa_extend(i, i);
        orig_pos[i] = sa_pos[i];
        st[sa_pos[i]].cnt++;
    }

    for (int i = 1; i < sz; i++)
        sparse[0][i] = st[i].link;

    for (int k = 1; k < LOG; k++)
        for (int i = 0; i < sz; i++)
            sparse[k][i] = sparse[k-1][sparse[k-1][i]];

    queue<int> q;
    for (int i=1; i<sz; i++) deg[st[i].link]++;
    for (int i=1; i<sz; i++) if (deg[i] == 0) q.push(i);
    while (!q.empty()) {
        int k = q.front();
        if (k > 0) {
            st[st[k].link].cnt += st[k].cnt;
            if ( --deg[st[k].link] == 0 ) q.push(st[k].link);
        }
        q.pop();
    }
}

int query(int p, int len)
{
    for (int k = LOG-1; k >= 0; k--) {
        if (st[sparse[k][p]].len >= len)
            p = sparse[k][p];
    }
    return st[p].cnt;
}

int query()
{
    int l, r;
    scanf("%d%d", &l, &r);
    int len = r - l + 1;
    int p = orig_pos[r-1];
    return query(p, len);
}

int main()
{
    int q;
    scanf("%d%d", &n, &q);
    scanf(" %s ", s);
    for (int i = 0; i < n; i++)
        a[i] = (int)(s[i] - 'a');
    solve();
    while(q--)
        printf("%d\n", query());

    return 0;
}