#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    if (n < 7) return cout << "0\n", void();
    k = min(k, 20);
    string p = "nanjing";
    int ans = 0;
    for (int i=0;i<=k;++i)
    {
        string t;
        for (int j=0;j<n;++j) t.push_back(s[(j + i) % n]);
        int sum = 0;
        for (int j=0;j+6<n;++j)
        {
            int o = 1;
            for (int k=0;k<7;++k) if (t[j + k] != p[k]) o = 0;
            if (o) ++sum;
        }
        ans = max(ans, sum);
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}