#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
const int N=2e5+10;

void solve()
{
    int n,k;
    string s;
    cin>>n>>k>>s;
    string t;
    // s+=s;
    int num=0, ans = 0;
    rep(i, 0, min(k, 7))
    {
        t = s;
        rotate(t.begin(), t.begin() + i, t.end());
        // cout << t << endl;
        num = 0;
        rep(j, 0, n - 7)
        {
            if(t.substr(j,7)=="nanjing")
                num++;
        }
        ans = max(ans, num);
    }
    cout<<ans<<endl;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}