#include <bits/stdc++.h>
using namespace std;
const int N = 1e4;
int n, q, cum[N][26];
char s[N + 1];
inline long long calc(int k, int ch) {
long long res = 1LL * k / n * cum[n - 1][ch];
if (k % n != 0)
res += cum[k % n - 1][ch];
return res;
}
int main(int argc, char **argv) {
int t;
scanf("%d", &t);
while (t-- != 0) {
scanf("%d%d%s", &n, &q, s);
memset(cum[0], 0, sizeof cum[0]);
++cum[0][s[0] - 'a'];
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 26; ++j)
cum[i][j] = cum[i - 1][j];
++cum[i][s[i] - 'a'];
}
int l, r;
char c;
while (q-- != 0) {
scanf("%d%d %c", &l, &r, &c);
printf("%lld\n", calc(r, c - 'a') - calc(l - 1, c - 'a'));
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTiA9IDFlNDsKaW50IG4sIHEsIGN1bVtOXVsyNl07CmNoYXIgc1tOICsgMV07CgppbmxpbmUgbG9uZyBsb25nIGNhbGMoaW50IGssIGludCBjaCkgewoJbG9uZyBsb25nIHJlcyA9IDFMTCAqIGsgLyBuICogY3VtW24gLSAxXVtjaF07CglpZiAoayAlIG4gIT0gMCkKCQlyZXMgKz0gY3VtW2sgJSBuIC0gMV1bY2hdOwoJcmV0dXJuIHJlczsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKiphcmd2KSB7CglpbnQgdDsKCXNjYW5mKCIlZCIsICZ0KTsKCXdoaWxlICh0LS0gIT0gMCkgewoJCXNjYW5mKCIlZCVkJXMiLCAmbiwgJnEsIHMpOwoJCW1lbXNldChjdW1bMF0sIDAsIHNpemVvZiBjdW1bMF0pOwoJCSsrY3VtWzBdW3NbMF0gLSAnYSddOwoJCWZvciAoaW50IGkgPSAxOyBpIDwgbjsgKytpKSB7CgkJCWZvciAoaW50IGogPSAwOyBqIDwgMjY7ICsraikKCQkJCWN1bVtpXVtqXSA9IGN1bVtpIC0gMV1bal07CgkJCSsrY3VtW2ldW3NbaV0gLSAnYSddOwoJCX0KCQlpbnQgbCwgcjsKCQljaGFyIGM7CgkJd2hpbGUgKHEtLSAhPSAwKSB7CgkJCXNjYW5mKCIlZCVkICVjIiwgJmwsICZyLCAmYyk7CgkJCXByaW50ZigiJWxsZFxuIiwgY2FsYyhyLCBjIC0gJ2EnKSAtIGNhbGMobCAtIDEsIGMgLSAnYScpKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==