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

void solve()
{
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    int res = 0;
    for(int i = 0; i <= min(7,k);i ++)
    {
        string tmp;
        int count = 0;
        for(int j = 0;j < n ;j ++)
        {
            tmp.push_back(s[(j + i) % n]);
        }
        for(int j = 0; j < n - 6;j ++)
        {
            string t;
            for(int k = j ;k < j + 7;k ++)
            {
                t.push_back(tmp[k]);
            }
            if(t == "nanjing")
            {
                count ++;
            }
        }
        res = max(count,res);
    }
    cout << res << endl;
}


int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}