#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int MAX = 3e5 + 5;

int kmp(string s1, string s2){
    int l1 = s1.size(), l2 = s2.size();
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    vector<int> nex(l2 + 1);
    int ans = 0;
    int j = 0;
    for (int i = 2; i <= l2; ++ i){
		while (j and s2[i] != s2[j + 1]) j = nex[j];
		if (s2[i] == s2[j + 1]) j ++;
		nex[i] = j;
    }
    j = 0;
    for (int i = 1; i <= l1; ++ i){
        while (j and s1[i] != s2[j + 1]) j = nex[j];
        if (s1[i] == s2[j + 1]) j ++;
        if (j == l2) ans ++, j = nex[j];
    }
    return ans;
}

void solve(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int ans = 0;
    string t = "nanjing";
    for (int i = 0; i < min(7, k + 1); i ++){
        string s2;
        for (int j = 0; j < n; j ++){
            s2 += s[(i + j) % n];
        }
        ans = max(ans, kmp(s2, t));
    }
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // cout << fixed << setprecision(10);
    int T;cin>>T;while (T--)
        solve();
}