#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e6+5;

// int pre[N];
void solve(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    if(n < 7){
        cout << 0 << endl;
        return ;
    }
    s = " " + s;
    for(int i = 1; i <= min(n, k); i++) s += s[i];
    vector<int>pre(2*n+5);
    int m = s.size() - 1;
    string t = "nanjing";
    for(int i=7; i<=m; i++){
        string cur = s.substr(i-7+1, 7);
        pre[i] = pre[i-1];
        if(cur == t) pre[i]++;
    }
    int ans = 0;
    for(int i=1; i+n-1<=m; i++){
        // [i,i+n-1]
        ans = max(ans, pre[i+n-1] - pre[i+7-2]);
    }
    cout << ans << endl;

}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}