// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever!

#include <bits/stdc++.h>


using namespace std;

// #define int long long 

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin>>T;
    while (T--) []{
        int n, k; cin>>n>>k;
        vector<int> a(2*n); string s; cin>>s; s+=s;
        for (int i=6; i<2*n; ++i)
            a[i]=a[i-1]+(s.substr(i-6,7)=="nanjing");
        int ans=0;
        for (int i=n-1; i<=min(n-1+k,2*n-1); ++i) {
            int cur=a[i];
            if (i-n>=0) cur-=a[i-n];
            ans=max(ans,cur);
        }
        cout<<ans<<'\n';
    }();

}