#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;

#ifdef LCX
#define msg(args...) fprintf(stderr, args)
#else
#define msg(...) void()
#endif

const int maxn = 1e5 + 10;
int n, q;
char s[maxn];
struct node {
    int l, r, k;
} a[maxn];
int ans[maxn];

int m, sa[maxn], rk[maxn], ht[maxn], tmp[maxn], cnt[maxn];
void radix_sort() {
    for (int i = 0; i <= m; ++i) cnt[i] = 0;
    for (int i = 1; i <= n; ++i) cnt[rk[tmp[i]]]++;
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
}
void buildSA() {
    fill(tmp, tmp + n * 2 + 1, 0);
    m = 'z';
    for (int i = 1; i <= n; ++i) rk[i] = s[i], tmp[i] = i;
    radix_sort();
    for (int w = 1, p = 0; p < n; w <<= 1, m = p) {
        p = 0;
        for (int i = n; i > n - w && i >= 1; --i) tmp[++p] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > w) tmp[++p] = sa[i] - w;
        radix_sort();
        for (int i = 1; i <= n; ++i) tmp[i] = rk[i];
        rk[sa[1]] = p = 1;
        for (int i = 2; i <= n; ++i) {
            if (tmp[sa[i]] != tmp[sa[i - 1]] ||
                tmp[sa[i] + w] != tmp[sa[i - 1] + w])
                ++p;
            rk[sa[i]] = p;
        }
    }
    ht[1] = 0;
    for (int i = 1, j = 0; i <= n; ++i) {
        if (rk[i] == 1) continue;
        if (j) --j;
        while (s[i + j] == s[sa[rk[i] - 1] + j]) ++j;
        ht[rk[i]] = j;
    }
}
const int B = 20;
struct ST {
    int mn[B][maxn];
    void build() {
        for (int i = 1; i <= n; ++i) mn[0][i] = ht[i];
        for (int i = 1; i < B; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
    }
    int ask(int l, int r) {
        int i = __lg(r - l + 1);
        return min(mn[i][l], mn[i][r - (1 << i) + 1]);
    }
} st;
int lcp(int p, int q) {
    p = rk[p], q = rk[q];
    if (p > q) swap(p, q);
    if (p == q) return n - q + 1;
    return st.ask(p + 1, q);
}
struct BIT {
    vi c;
    int N;
    void init(int n) { N = n, c.assign(N + 1, 0); }
    void add(int x, int y) {
        for (; x <= N; x += x & -x) c[x] += y;
    }
    int ask(int x) {
        int res = 0;
        for (; x > 0; x &= x - 1) res += c[x];
        return res;
    }
    int ask(int l, int r) {
        if (l > r) return 0;
        return ask(r) - ask(l - 1);
    }
} tr;

void solve1() {
    vector <vi> vec(n + 1);
    for (int i = 1; i <= q; ++i)
        vec[rk[a[i].k]].push_back(i);
    tr.init(n);
    for (int i = 1; i <= n; ++i) {
        for (int o : vec[i])
            ans[o] += tr.ask(a[o].l, a[o].r);
        tr.add(sa[i], 1);
    }
}

void solve2() {
    vector <vi> vec(n + 1);
    for (int i = 1; i <= q; ++i) {
        int l = 1, r = rk[a[i].k], res = rk[a[i].k];
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (lcp(sa[mid], a[i].k) >= a[i].r - a[i].k + 1)
                res = mid, r = mid - 1;
            else l = mid + 1;
        }
        if (res < rk[a[i].k])
            vec[res - 1].push_back(-i),
            vec[rk[a[i].k] - 1].push_back(i);
    }
    tr.init(n);
    for (int i = 1; i <= n; ++i) {
        tr.add(sa[i], 1);
        for (int o : vec[i]) {
            int c = o / abs(o);
            o = abs(o);
            ans[o] -= c * tr.ask(a[o].l, a[o].k - 1);
        }
    }
}

void solve3() {
    vector <vi> vec(n + 1);
    for (int i = 1; i <= n; ++i)
        vec[rk[a[i].k]].push_back(i);
    tr.init(n);
    function <void(int, int)> solve =
    [&] (int l, int r) -> void {
        if (l == r) return;
        int mid = (l + r) >> 1;
        solve(l, mid), solve(mid + 1, r);
        static int mn[maxn];
        mn[mid] = mn[mid + 1] = ht[mid + 1];
        for (int i = mid; i >= l; --i)
            mn[i] = min(mn[i + 1], ht[i + 1]);
        for (int i = mid + 1; i <= r; ++i)
            mn[i] = min(mn[i - 1], ht[i]);
        vi vq;
        for (int i = l; i <= mid; ++i)
            for (int o : vec[i]) vq.push_back(o);
        sort(begin(vq), end(vq), [&] (int p, int q) {
            return a[p].r > a[q].r;
        });
        vi va;
        for (int i = mid + 1; i <= r; ++i)
            va.push_back(i);
        sort(begin(va), end(va), [&] (int p, int q) {
            return sa[p] + mn[p] > sa[q] + mn[q];
        });
        int j = 0, len = va.size();
        for (int o : vq) {
            while (j < len && sa[va[j]] + mn[va[j]] >= a[o].r + 1)
                tr.add(sa[va[j]], 1), ++j;
            ans[o] += tr.ask(max(a[o].r - mn[rk[a[o].k]] + 1, a[o].k + 1), a[o].r);
        }
        while (j) --j, tr.add(sa[va[j]], -1);
    };
    solve(1, n);
}

void work() {
    scanf("%d%d%s", &n, &q, s + 1);
    for (int i = 1; i <= q; ++i)
        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].k), ans[i] = 0;
    buildSA();
    msg("SA:\n");
    for (int i = 1; i <= n; ++i) msg("%d%c", sa[i], " \n"[i == n]);
    msg("rk:\n");
    for (int i = 1; i <= n; ++i) msg("%d%c", rk[i], " \n"[i == n]);
    msg("ht:\n");
    for (int i = 1; i <= n; ++i) msg("%d%c", ht[i], " \n"[i == n]);
    st.build();
    solve1();
    solve2();
    solve3();
    for (int i = 1; i <= q; ++i)
        printf("%d\n", ans[i] + 1);
}

int main() {
    int T; scanf("%d", &T);
    while (T --> 0) work();
    return 0;
}