#include <bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define ull unsigned long long
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
const int N = 310, M = 5e3 + 10, INF = 1e18, mod = 1e9 + 7;
// const int P1 = 6907, P2 = 13331, mod1 = 998244353, mod2 = 1e9+9;

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i <= n - 7; i++)
    {
        if(s.substr(i,7)=="nanjing")
            cnt++;
    }
    for (int j = 1; j <= min(10ll,min(n,k));j++) 
    {
        string s2 = s.substr(j) + s.substr(0, j);
        int now = 0;
        for (int i = 0; i <= n - 7; i++)
        {
            if (s2.substr(i, 7) == "nanjing")
                now++;
        }
        cnt = max(cnt, now);
    }
    cout << cnt << endl;
}

signed main()
{
    ios;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}