#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n,k;
void solve() {
    cin>>n>>k;
    string s;
    cin>>s;
    string t="nanjing";
    k=min(9,k+1);
    int ans=0;
    while(k--){
        // cout<<s<<"\n";
        int cur=0;
        for(int i=0;i+7-1<=n;i++){
            int flag=1;
            for(int j=0;j<7;j++){
                if(t[j]!=s[i+j-1]){
                    flag=0;
                    break;
                }
            }
            cur+=flag;
        }
        // cout<<cur<<"\n";
        ans=max(ans,cur);
        char c=s[0];
        s.erase(s.begin());
        s.push_back(c);
    }
    cout<<ans<<"\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}