#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

struct polyhash {
    ll n, mod;
    string s;
    vector<ll> h, ppow;
    polyhash() = default;
    polyhash(int n_, string s_, ll p, ll md) {
        n = n_; s = s_;
        mod = md;   
        h.assign(n + 1, 0);
        ppow.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            ppow[i] = (ppow[i - 1] * p) % mod;
            h[i] = (h[i - 1] * p + s[i - 1] - 'a' + 1) % mod;
        }
    }

    ll diff(ll x, ll y) {
        return (x - y >= 0 ? x - y : x - y + mod);
    }

    ll substr(int l, int r) {
        return diff(h[r + 1], (h[l] * ppow[r - l + 1]) % mod);
    }
};

struct sparsetable {
    int n;
    vector<int> vals;
    vector<vector<int>> sp;
    sparsetable() = default;
    sparsetable(int n_, vector<int> vals_) {
        n = n_;
        vals = vals_;
        sp.assign(18, vector<int>(n));
        for (int i = 0; i < n; i++) sp[0][i] = vals[i];
        for (int i = 1; i < 18; i++) {
            for (int j = 0; j + (1 << i) - 1 < n; j++) sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }

    int get(int l, int r) {
        if (l > r) swap(l, r);
        int lg = 31 - __builtin_clz(r - l + 1);
        return min(sp[lg][l], sp[lg][r - (1 << lg) + 1]);
    }
};

struct sufarr {
    int n;
    string s;
    vector<int> c, ord, ord2, cnt, curind, pos;
    vector<pair<int, int>> lol;
    vector<int> lcp;
    sparsetable sp_lcp;
    sufarr(int n_, string s_) {
        n = n_;
        s = s_;
        n++;
        s += '!';
        c.resize(n);
        ord.assign(n, 0);
        ord2.assign(n, 0);
        iota(all(ord2), 0);
        lol.resize(n);
        lcp.assign(n - 1, 0);
        cnt.assign(n, 0); curind.assign(n, 0);
        build();
        calc_lcp();
    }

    void rsort() {
        for (int i = 0; i < n; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[lol[i].second]++;
        int ci = 0;
        for (int i = 0; i < n; i++) {curind[i] = ci; ci += cnt[i];}
        {
            for (int i = 0; i < n; i++) ord[curind[lol[i].second]++] = i;
        }
        {
            ci = 0;
            for (int i = 0; i < n; i++) {curind[i] = ci; ci += cnt[i];}
            for (int i = 0; i < n; i++) ord2[curind[lol[ord[i]].first]++] = ord[i];
        }
        // ans in ord2
    }

    void build() {
        vector<int> inds(n);
        iota(all(inds), 0);
        sort(all(inds), [&](int i, int j) {return s[i] < s[j];});
        // 
        c[inds[0]] = 0;
        int cur = 0;
        for (int i = 1; i < n; i++) {
            if (s[inds[i]] != s[inds[i - 1]]) cur++;
            c[inds[i]] = cur;
        }

        for (int len = 1; len <= n; len *= 2) {
            for (int i = 0; i < n; i++) {
                lol[i] = {c[i], c[(i + len >= n ? i + len - n : i + len)]};
            }
            //sort(all(ord2), [&](int i, int j){return lol[i] < lol[j];});
            rsort();
            int cur = 0;
            c[ord2[0]] = 0;
            for (int i = 1; i < n; i++) {
                if (lol[ord2[i]] != lol[ord2[i - 1]]) cur++;
                c[ord2[i]] = cur;
            }
        }
        pos.assign(n, 0);
        for (int i = 0; i < sz(ord2); i++) pos[ord2[i]] = i;
    }

    void calc_lcp() {
        polyhash pl1(n, s, 31, 1e9 + 7), pl2(n, s, 31, 998244353);
        for (int i = 0; i < sz(ord2) - 1; i++) {
            int L = 0, R = min(n - ord2[i], n - ord2[i + 1]) + 1;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (pl1.substr(ord2[i], ord2[i] + M - 1) == pl1.substr(ord2[i + 1], ord2[i + 1] + M - 1) && 
                    pl2.substr(ord2[i], ord2[i] + M - 1) == pl2.substr(ord2[i + 1], ord2[i + 1] + M - 1)) L = M;
                else R = M;
            }
            lcp[i] = L;
        }
        sp_lcp = sparsetable(sz(lcp), lcp);
        // for (int el : ord2) {
        //     for (int j = el; j < n; j++) cout << s[j];
        //     cout << '\n';
        // }
        // for (int el : lcp) cout << el << '\n';
    }

    int get_lcp(int ind1, int ind2) {
        return (ind1 == ind2 ? n - ord2[ind1] : sp_lcp.get(ind1, ind2 - 1));
    }

    int get_lcp_by_vals(int val1, int val2) {
        return (val1 == val2 ? n - val1 : sp_lcp.get(min(pos[val1], pos[val2]), max(pos[val2], pos[val1]) - 1));
    }
};

struct fenwick {
    int n;
    vector<int> t;
    fenwick() = default;
    fenwick(int n_) {
        n = n_;
        t.assign(n + 1, 0);
    }
 
    void upd(int p, int vl) {
        for (; p <= n; p = (p | (p + 1))) t[p] += vl;
    }
 
    int get(int p) {
        int sm = 0;
        for (; p > 0; p = (p & (p + 1)) - 1) sm += t[p];
        return sm;
    }
};

void solve(int c) {
    int n, q; cin >> n >> q;
    string s; cin >> s;
    string rs = s; reverse(all(rs));
    sufarr sf(2 * n, s + rs);
    vector<int> order_rev;
    for (int el : sf.ord2) {
        if (el >= n && el < 2 * n) order_rev.pb(el - n);
    }

    auto check = [&](int ls, int rs, int lr, int rr) {
        return sf.get_lcp_by_vals(ls, n + lr) >= rs - ls + 1;
    };

    auto compare = [&](int is, int irs) -> bool {
        int lc = sf.get_lcp_by_vals(is, irs + n);
        if (lc == min(n - is, n - irs)) return (n - is == lc);
        return s[is + lc] <= rs[irs + lc];
    };

    auto compare2 = [&](int ls, int RS, int LR, int rr) -> bool {
        int lc = sf.get_lcp_by_vals(ls, n + LR);
        if (lc >= RS - ls + 1) {
            return 0;
        }
        return s[ls + lc] < rs[LR + lc];
    };

    if (n <= 4000 && q <= 4000) {
        for (int ind = 0; ind < q; ind++) {
            int i, r; cin >> i >> r;
            i--;
            int answ = 0;
            for (int len = 1; len <= r; len++) {
                answ += compare2(i, i + len - 1, n - 1 - (i + 2 * len - 1), -1);
            }
            cout << answ << '\n';
            continue;
        }   
        return;
    }

    vector<vector<array<int, 3>>> reqs(sz(order_rev) + 1);
    vector<int> limitt(q);
    vector<pair<int, int>> queries(q);
    for (int ind = 0; ind < q; ind++) {
        int i, r; cin >> i >> r;
        limitt[ind] = r;
        i--;
        queries[ind] = {i, r};

        int L = -1, R = sz(order_rev);
        while (R - L > 1) {
            int M = (L + R) / 2;
            if (compare(i, order_rev[M])) R = M;
            else L = M;
        }
        reqs[R].pb({i, 1 - i % 2, ind});
    }
    vector<int> ans(q);
    fenwick fw_chet(n + 10), fw_nech(n + 10);
    for (int i = n - 1; i >= 0; i--) {
        int norm_ind = n - order_rev[i] - 1;
        if (norm_ind % 2) fw_nech.upd(norm_ind + 1, 1);
        else fw_chet.upd(norm_ind + 1, 1);
        for (auto qr : reqs[i]) {
            if (qr[1] == 0) {
                ans[qr[2]] += fw_chet.get(2 * limitt[qr[2]] + qr[0]) - fw_chet.get(qr[0]);
            } else {
                ans[qr[2]] = fw_nech.get(2 * limitt[qr[2]] + qr[0]) - fw_nech.get(qr[0]);
            }
        }
    }

    if (10 <= c && c <= 14) {
        vector<int> maxpal(n);
        for (int i = 0; i < n; i++) {
            int len = 0;
            while (len <= 25 && len + 1 <= min(i + 1, n - (i + 1)) && s[i - len] == s[i + 1 + len]) len++;
            maxpal[i] = len;
        }
        for (int i = 0; i < q; i++) {
            int ind = queries[i].first;

            for (int len = 1; len <= min(25, queries[i].second); len++) {
                if (ind + 2 * len - 1 >= n) break;
                if (compare(ind, n - (ind + 2 * len - 1) - 1) && maxpal[ind + len - 1] >= len) {
                    ans[i]--;
                } 
            }
        }
    }

    for (int el : ans) cout << el << '\n';
}

signed main() {
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(false);

    int c, t; cin >> c >> t;
    while (t--) {
        solve(c);
    }

    return 0;
}