#include <bits/stdc++.h>
using namespace std;
void sol()
{
    int N, K;
    cin >> N >> K;
    string str;
    cin >> str;
    vector<int> is_hok(N, 0);
    vector<int> pre(N, 0);
    string str_cmp = "nanjing";
    if (str.size() < 7)
    {
        cout << "0\n";
        return;
    }
    for (int i = 0; i < N; i++)
    {
        bool is_ok = true;
        for (int j = 0; j < 7; j++)
        {
            if (str[(i + j) % N] != str_cmp[j])
            {
                is_ok = false;
                break;
            }
        }
        if (is_ok)
        {
            is_hok[i] = 1;
        }
    }
    for (int i = 0; i < N; i++)
    {
        pre[i] = (i != 0 ? pre[i - 1] : 0) + is_hok[i];
    }
    int ans = 0;
    for (int i = 0; i <= min(K, N - 1); i++)
    {
        if (i >= 7)
            ans = max(ans, pre[N - 1] - (pre[i] - pre[max(i - 6, 0)]));
        else
            ans = max(ans, pre[N - 1] - (pre[i] - pre[0] + pre[N - 1] - pre[N - 1 - (6 - i) + 1]));
    }
    cout << ans << "\n";
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        sol();
    }
}