#include <bits/stdc++.h>

#define int long long

std::string s = "nanjing";
void solve()
{
    int n, k;
    std::string t;
    std::cin >> n >> k >> t;
    if (n < 7)
    {
        std::cout << 0 << '\n';
        return;
    }
    t = ' ' + t + t;
    std::vector<int> val(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n - 6; ++i)
    {
        bool ok = 1;
        for (int j = i; j <= i + 6; ++j)
        {
            if (t[j] != s[j - i])
            {
                ok = 0;
                break;
            }
        }
        val[i] = ok;
    }
    for (int i = 2; i <= 2 * n - 6; ++i)
    {
        val[i] += val[i - 1];
    }
    int ans = 0;
    for (int i = 1; i <= std::min(k + 1, n); ++i) // 枚举起点
    {
        ans = std::max(ans, val[i + n - 6 - 1] - val[i - 1]);
    }
    std::cout << ans << '\n';
}

signed main()
{

    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

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