#include <bits/stdc++.h>
using namespace std;
#define _11037_ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl '\n'
#define MAX 400005
#define MOD 998244353
int ans, len, stop, pres[MAX], pret[MAX];
int T, n, k;
string s;
void init(void)
{
    ans = 0;
    for (int i = 0; i < n * 2 + 1; i++)
        pres[i] = pret[i] = 0;
}
signed main()
{
    _11037_
    cin >> T;
    while (T--)
    {
        cin >> n >> k >> s, len = s.length();
        s = " " + s + s;
        stop = min((int)s.length(), len + k + 1);
        init();
        for (int i = 1; i < stop; i++)
        {
            if (i + 6 < stop && s.substr(i, 7) == "nanjing")
                pres[i]++, pret[i + 6]++;
            pres[i] = pres[i] + pres[i - 1];
            pret[i] = pret[i] + pret[i - 1];
        }
        for (int i = 1; i + len - 1 < stop; i++)
            ans = max(ans, pret[i + len - 1] - pres[i - 1]);
        cout << ans << endl;
    }
}