#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define endl '\n'
void Solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = s + s;
    string p = "nanjing";
    int m = p.size();
    vector<int> v;
    for (int i = 0; i + m - 1 < 2 * n; i++)
    {
        if (s.substr(i, m) == p)
            v.push_back(i);
    }
    int res = 0;
    for (int i = 0; i <= k && i < n; i++)
    {
        int j = i + n - 1;
        int L = lower_bound(v.begin(), v.end(), i) - v.begin();
        int R = upper_bound(v.begin(), v.end(), j - m + 1) - v.begin() - 1;
        if (L > R || L >= v.size() || R < 0)
            continue;
        res = max(res, R - L + 1);
    }
    cout << res << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        Solve();
}