#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'


const string str="nanjing";

void solve(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s+=s;
    deque<int > Q;
    int ans=0;
    for(int i=0;i<=min(n+k-7,2*n-7);i++){
        int ok=1;
        for(int j=0;j<7;j++){
            if(s[i+j]!=str[j]){
                ok=0;
                break;
            }
        }

        if(ok==1){
            Q.push_back(i);
        }

        if(!Q.empty()&&i-Q.front()>n-7){
            Q.pop_front();
        }
        ans=max(ans,(int)Q.size());
    }
    cout<<ans<<endl;
}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    
    return 0;
}