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

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s += s;

    k = min(k, 14LL);
    int ans = 0;
    for (int i = 0; i <= min(k, n - 1); i++)
    {
        int cnt = 0;
        for (int j = i; j < n + i - 6; j++)
        {
            if (s.substr(j, 7) == "nanjing")
            {
                cnt++;
                j = j + 6;
            }
        }

        ans = max(ans, cnt);
    }
    // for (int i = 0; i < k; i++)
    // {
    //     for (int j = i; j < n + i - 6; j++)
    //     {
    //         cout << s[j];
    //     }
    //     cout << '\n';
    // }

    cout << ans << '\n';
}

signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}