#include <bits/stdc++.h>
using namespace std;
constexpr int N = 4e5 + 10;
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define endl '\n'
char s[N];
int n, k;
const string val = "nanjing";

inline void solve()
{
    cin >> n >> k;
    k = min(n, k);
    forn(i, 1, n)cin >> s[i], s[i + n] = s[i];
    if (n < val.length())
    {
        cout << 0 << endl;
        return;
    }
    int ans = 0, l = 0;
    int res = 0;
    forn(r, 1, n+k)
    {
        if (r >= val.length())
        {
            string top;
            forn(i, r-val.length()+1, r)top += s[i];
            ans += top == val;
        }
        res = max(ans, res);
        if (r >= n)
        {
            string top;
            forn(i, l, l+val.length()-1)top += s[i];
            ans -= top == val;
            ++l;
        }
    }
    cout << res << endl;
}

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)solve();
    return 0;
}