#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 200009;
typedef long long ll;

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int op = min(100, k);
    int num = 0;
    for (int u = 0; u <= op; u++)
    {
        // string q;
        int v = 0;
        for (int i = 0; i < n; i++)
        {
            if (n - i >= 7)
            {
                string q = s.substr(i, 7);
                if (q == "nanjing")
                    v++;
            }
        }
        num = max(num, v);
        auto f = *s.begin();
        s.erase(s.begin());
        s += f;
    }
    cout << num << '\n';
}

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