#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int T, n, q;
char s[MAXN];
int sa[MAXN], rk[MAXN], tmp[MAXN], cnt[MAXN];
int h[MAXN];
void getSuffixArray() {
    int m = 255;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
    for (int w = 1, t = 0; ; m = t, t = 0, w <<= 1) {
        for (int i = 1; i <= n; i++) if (i + w > n) tmp[++t] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > w) tmp[++t] = sa[i] - w;
        for (int i = 1; i <= m; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) cnt[rk[tmp[i]]]++;
        for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
        swap(tmp, rk), t = 0;
        for (int i = 1; i <= n; i++) {
            rk[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w]) ? t : ++t;
        }
        if (t == n) return;
    }
}
void getHeight() {
    for (int i = 1; i <= n; i++) h[i] = 0;
    for (int i = 1, j = 0; i <= n; i++) {
        if (j) j--;
        while (s[i + j] == s[sa[rk[i] - 1] + j]) j++;
        h[rk[i]] = j;
    }
}
int st[MAXN][17];
void init() {
    for (int i = 1; i <= n; i++) st[i][0] = h[i];
    for (int j = 1; j <= 16; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int lcp(int i, int j) {
    int len = __lg(j - i + 1);
    return min(st[i][len], st[j - (1 << len) + 1][len]);
}
struct BinaryIndexTree {
    int a[MAXN];
#define lowbit(x) (x & (-x))
    void add(int d, int v) {
        while (d < MAXN) {
            a[d] += v;
            d += lowbit(d);
        }
    }
    int query(int d) {
        int ret = 0;
        while (d) {
            ret += a[d];
            d -= lowbit(d);
        }
        return ret;
    }
    int query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
} bit;
int ans[MAXN];
int l[MAXN], r[MAXN], k[MAXN];
struct Query {
    int l, r, i, k;
    bool operator<(const Query &b) const { return l < b.l; }
};
vector<Query> qs[MAXN];
int v[MAXN];
void solve(int l, int r, vector<int> q) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    vector<int> ql, qr;
    for (int i : q) if (rk[k[i]] <= mid) ql.push_back(i); else qr.push_back(i);
    solve(l, mid, ql), solve(mid + 1, r, qr);
    v[mid] = INT_MAX / 2;
    for (int i = mid + 1; i <= r; i++) v[i] = min(v[i - 1], h[i]);
    for (int i = mid - 1; i >= 1; i--) v[i] = min(v[i + 1], h[i + 1]);
    vector<pair<int, int>> opt;
    vector<Query> qry;
    for (int i : ql) {
        int L = max(::r[i] - v[rk[k[i]]] + 1, k[i] + 1), R = ::r[i];
        qry.push_back({ L - 1, ::r[i] + 1, i, -1 });
        qry.push_back({ R, ::r[i] + 1, i, 1 });
    }
    for (int i = mid + 1; i <= r; i++) opt.push_back({ sa[i], v[i] + sa[i] });
    sort(opt.begin(), opt.end()), sort(qry.begin(), qry.end());
    auto it = opt.begin();
    for (auto p : qry) {
        while (it != opt.end() && it->first <= p.l) bit.add(it->second, 1), it++;
        ans[p.i] += p.k * bit.query(p.r, 2 * n);
    }
    while (it != opt.begin()) it--, bit.add(it->second, -1);
}
int main() {
    // freopen("a.in", "r", stdin);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%s", &n, &q, s + 1);
        getSuffixArray();
        getHeight();
        init();
        for (int i = 1; i <= q; i++) scanf("%d%d%d", &l[i], &r[i], &k[i]), ans[i] = 0;
        for (int i = 1; i <= n; i++) qs[i].clear();
        for (int i = 1; i <= q; i++) {
            qs[l[i] - 1].push_back({ rk[k[i]], 0, i, -1 });
            qs[r[i]].push_back({ rk[k[i]], 0, i, 1 });
        }
        for (int i = 1; i <= n; i++) {
            bit.add(rk[i], 1);
            for (auto p : qs[i]) ans[p.i] += p.k * bit.query(p.l);
        }
        // for (int i = 1; i <= q; i++) printf("%d ", ans[i]);
        // printf("\n");
        for (int i = 1; i <= n; i++) bit.add(rk[i], -1);
        for (int i = 1; i <= n; i++) qs[i].clear();
        for (int i = 1; i <= q; i++) {
            int L = 1, R = rk[k[i]];
            while (L < R) {
                int mid = (L + R) >> 1;
                if (lcp(mid + 1, rk[k[i]]) >= r[i] - k[i] + 1) R = mid;
                else L = mid + 1;
            }
            qs[L - 1].push_back({ l[i], k[i] - 1, i, -1 });
            qs[rk[k[i]] - 1].push_back({ l[i], k[i] - 1, i, 1 });
        }
        for (int i = 1; i <= n; i++) {
            bit.add(sa[i], 1);
            for (auto p : qs[i]) ans[p.i] -= p.k * bit.query(p.l, p.r);
        }
        // for (int i = 1; i <= q; i++) printf("%d ", ans[i]);
        // printf("\n");
        for (int i = 1; i <= n; i++) bit.add(sa[i], -1);
        vector<int> qq;
        for (int i = 1; i <= q; i++) qq.push_back(i);
        solve(1, n, qq);
        for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
        // printf("\n");
    }
    return 0;
}
/*
baaabbabba

1 a          10
2 aaabbabba  2
3 aabbabba   3
4 abba       7
5 abbabba    4
6 ba         9
7 baaabbabba 1
8 babba      6
9 bba        8
X bbabba     5

*/