#include <bits/stdc++.h>
using namespace std;
const string nj = "nanjing";
void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    auto work = [&](const string &s)
    {
        int cnt = 0;
        string_view sv(s);
        for (int i = 0; i < n; i++)
        {
            if (sv.substr(i, 7) == nj)
                cnt++;
        }
        return cnt;
    };
    int res = 0;
    res = max(res, work(s));
    for (int i = 0; i < k && i < 7; i++)
    {
        s.push_back(s.front());
        s.erase(s.begin());
        res = max(res, work(s));
    }
    cout << res << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}