#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define ff first
#define ss second

const int N = 1024 * 1024;
ll tree[2 * N][3];

struct quer{
    int l, r, ind;
};

void upd(int v, ll val, int t){
    v += N;
    while(v) {
        tree[v][t] += val;
        v >>= 1;
    }
}

ll query(int l, int r, int t){
    l += N;
    r += N;
    ll wyn = 0;
    while(l <= r) {
        if(l & 1) wyn += tree[l++][t];
        if(!(r & 1)) wyn += tree[r--][t];
        l >>= 1; r >>= 1;
    }
    return wyn;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    string s, t = "^#";
    cin >> s;
    for(char c : s){
        t += c;
        t += '#';
    }
    t += '$';

    int m = t.size();
    vi p(m, 0);
    int g = 0, manacher = 0;

    for(int i = 1; i < m - 1; i++){
        int odwr = 2 * g - i;
        if(manacher > i){
            p[i] = min(manacher - i, p[odwr]);
        }else{
            p[i] = 0;
        }
        while(t[i + 1 + p[i]] == t[i - 1 - p[i]]) p[i]++;

        if(i + p[i] > manacher) {
            g = i;
            manacher = i + p[i];
        }
    }

    vi pr(2 * n + 1), cl(2 * n + 1), cr(2 * n + 1), grl(2 * n + 1), grr(2 * n + 1);
    for(int x = 2; x <= 2 * n; x++){
        cl[x] = x / 2;
        cr[x] = (x + 1) / 2;
        pr[x] = (p[x] + 1) / 2;
        grl[x] = cl[x] - pr[x];
        grr[x] = cr[x] + pr[x];
    }

    vector<vector<quer>> ql(n + 1), qr(n + 1);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        ql[l].pb({l, r, i});
        qr[r].pb({l, r, i});
    }

    vll wyn(q, 0);
    vector<vi> el(n + 2);

    for(int x = 2; x <= 2 * n; x++){
        upd(x, cl[x] + 1, 1);
        upd(x, 1, 2);

        int tr = grl[x] + 1;
        if(tr > n) tr = n + 1;
        if(tr >= 1) el[tr].pb(x);
    }

    for(int aktl = n + 1; aktl >= 1; aktl--){
        for(int x : el[aktl]) {
            upd(x, -(cl[x] + 1), 1);
            upd(x, -1, 2);
            upd(x, pr[x], 0);
        }

        if(aktl <= n){
            for(auto &zap : ql[aktl]){
                int aktr = zap.r;
                ll s1 = query(2 * aktl, aktl + aktr, 0);
                ll s2c = query(2 * aktl, aktl + aktr, 1);
                ll s2cnt = query(2 * aktl, aktl + aktr, 2);

                wyn[zap.ind] += s1 + s2c - 1ll * aktl * s2cnt;
            }
        }
    }

    vector<vi> er(n + 1);
    
    for(int i = 0; i < 2 * N; i++){
    	tree[i][0] = 0; tree[i][1] = 0; tree[i][2] = 0;
    }

    for(int x = 2; x <= 2 * n; x++){
        upd(x, cr[x] - 1, 1);
        upd(x, 1, 2);

        int tr = grr[x] - 1;
        if(tr < 0) tr = 0;
        if(tr <= n) er[tr].pb(x);
    }

    for(int aktr = 0; aktr <= n; aktr++){
        for(int x : er[aktr]){
            upd(x, -(cr[x] - 1), 1);
            upd(x, -1, 2);
            upd(x, pr[x], 0);
        }

        if(aktr >= 1){
            for(auto &zap : qr[aktr]){
                int aktl = zap.l;
                ll s1 = query(aktl + aktr + 1, 2 * aktr, 0);
                ll s2c = query(aktl + aktr + 1, 2 * aktr, 1);
                ll s2cnt = query(aktl + aktr + 1, 2 * aktr, 2);

                wyn[zap.ind] += s1 + 1LL * aktr * s2cnt - s2c;
            }
        }
    }

    for(int i = 0; i < q; i++){
        cout << wyn[i] << "\n";
    }

    return 0;
}