#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = long long;
string ans = "nanjing";
void solve()
{
    int n, k;
    cin >> n >> k;
    string S;
    cin >> S;
    int m = S.size();
    S += S;

    int st = min(n - 1 + k, 2 * n - 1), start = 0;
    for(int i = st; i >= 0; i--) {
        if(i - 6 < 0) break;
        for(int j = 0; j <= 6; j++) {
            if(ans[6 - j] != S[i - j]) break;
            if(j == 6) {
                start = i;
                break;
            }
        }
        if(start) break;
    }

    int cnt = 0;
    for(int i = start; i >= 0 && i > start - n; i--) {
        if(i - 6 < 0) break;
        for(int j = 0; j <= 6; j++) {
            if(ans[6 - j] != S[i - j]) break;
            if(j == 6) {
                cnt++;
            }
        }
    }
    cout << cnt << '\n';
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}