#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;

    if (k > n)
    {
        k %= n;
        if (k == 0)
            k = n;

        k = min(k, 7LL);
    }
    int ans = 0;
    for (int i = 0; i <= k; 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;
}