#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

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

typedef pair<int, int> pii;
#define mp make_pair
typedef vector<pii> vec;
typedef pair<vec, int> pvi;

char s[N];
int a[N];
int lst[K];
int SA[N], nSA[N];
int col[N], ncol[N];
int b[N];
int revSA[N];
int LCP[N];
int sparse[LOG][N];
int p2[N];
int n;
vector<int> specPos[N];
pvi arr[N];
int revArr[N];

void buildSA()
{
    a[n++] = 0;
    for (int i = 0; i <= n; i++)
        b[n] = 0;
    for (int i = 0; i < n; i++)
        b[a[i] + 1]++;
    for (int i = 0; i < n; i++)
        b[i + 1] += b[i];
    for (int i = 0; i < n; i++)
        SA[b[a[i]]++] = i;
    col[SA[0]] = 0;
    for (int i = 1; i < n; i++)
    {
        col[SA[i]] = col[SA[i - 1]];
        if (a[SA[i]] != a[SA[i - 1]])
            col[SA[i]]++;
    }
    for (int len = 1; col[SA[n - 1]] < n - 1; len <<= 1)
    {
        for (int i = 0; i <= n; i++)
            b[i] = 0;
        for (int i = 0; i < n; i++)
            b[col[i] + 1]++;
        for (int i = 0; i < n; i++)
            b[i + 1] += b[i];
        for (int i = 0; i < n; i++)
        {
            int p = (SA[i] - len + 4 * n) % n;
            nSA[b[col[p]]++] = p;
        }
        for (int i = 0; i < n; i++)
            SA[i] = nSA[i];
        ncol[SA[0]] = 0;
        for (int i = 1; i < n; i++)
        {
            int p = SA[i], q = SA[i - 1];
            ncol[p] = ncol[q];
            if (col[p] != col[q] || col[(p + len) % n] != col[(q + len) % n])
                ncol[p]++;
        }
        for (int i = 0; i < n; i++)
            col[i] = ncol[i];
    }
    for (int i = 0; i < n; i++)
        revSA[SA[i]] = i;
    int curLCP = 0;
    for (int i = 0; i < n; i++)
    {
        int p = revSA[i];
        if (p == n - 1)
        {
            LCP[p] = curLCP = 0;
            continue;
        }
        curLCP = max(0, curLCP - 1);
        int q = SA[p + 1];
        while(i + curLCP < n && q + curLCP < n && a[i + curLCP] == a[q + curLCP])
            curLCP++;
        LCP[p] = curLCP;
    }
    n--;
    for (int i = 0; i < n; i++)
        sparse[0][i] = LCP[i];
    for (int k = 1; k < LOG; k++)
        for (int i = 0; i + (1 << k) <= n; i++)
            sparse[k][i] = min(sparse[k - 1][i], sparse[k - 1][i + (1 << (k - 1))]);
    for (int i = 2; i < N; i++)
        p2[i] = p2[i >> 1] + 1;
    return;
}

int getSparse(int l, int r)
{
    int k = p2[r - l];
    return min(sparse[k][l], sparse[k][r - (1 << k)]);
}
int getLCP(int l, int r)
{
    if (l == r)
        return n - SA[l];
    if (l > r) swap(l, r);
    return getSparse(l, r);
}

int getPosInSA(int pos, int len)
{
    pos = revSA[pos];
    int l = -1, r = pos;
    while(r - l > 1)
    {
        int x = (l + r) / 2;
        if (getLCP(x, pos) >= len)
            r = x;
        else
            l = x;
    }
    return r;
}

void solve()
{
    for (int i = 0; i < K; i++)
        lst[i] = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (lst[a[i]] != -1)
            a[lst[a[i]]] = lst[a[i]] - i + 1;
        lst[a[i]] = i;
        a[i] = 1;
        specPos[i].clear();
        for (int j = 0; j < K; j++)
            if (lst[j] != -1)
                specPos[i].push_back(lst[j]);
        sort(specPos[i].begin(), specPos[i].end());
        specPos[i].push_back(n);
    }
    buildSA();
    for (int i = 0; i < n; i++)
    {
        vec cur;
        for (int j = 0; j < (int)specPos[i].size() - 1; j++)
        {
            int curPos = specPos[i][j] + 1;
            int len = specPos[i][j + 1] - curPos;
            cur.push_back(mp(getPosInSA(curPos, len), len));
        }
        arr[i] = mp(cur, i);
    }
    sort(arr, arr + n);
    /*
    for (int i = 0; i < n; i++)
    {
        printf("%d : ", arr[i].second);
        for (pii p : arr[i].first)
            printf("(%d %d) ", p.first, p.second);
        printf("\n");
    }
    */
    for (int i = 0; i < n; i++)
        revArr[arr[i].second] = i;
    return;
}

bool equalToLen(vec A, vec B, int len)
{
    for (int i = 0;; i++)
    {
        if (len <= 0) return true;
        if (i >= (int)A.size() || i >= (int)B.size()) return false;
        len--;
        if (len > min(A[i].second, B[i].second))
        {
            if (A[i] != B[i]) return false;
            len -= A[i].second;
            continue;
        }
        return getLCP(A[i].first, B[i].first) >= len;
    }
    throw;
}

int query(int p, int len)
{
    int l = -1, r = p;
    while(r - l > 1)
    {
        int x = (l + r) / 2;
        if (equalToLen(arr[x].first, arr[p].first, len))
            r = x;
        else
            l = x;
    }
    int L = r;
    l = p;
    r = n;
    while(r - l > 1)
    {
        int x = (l + r) / 2;
        if (equalToLen(arr[x].first, arr[p].first, len))
            l = x;
        else
            r = x;
    }
    int R = r;
    return R - L;
}

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

int main()
{
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    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;
}