#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

string t = "nanjing";

void sol()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    vector<int>a(n, 0);
    int ans = 0, mn = 1e9;
    for (int i = 0; i < n; i ++)
    {
        bool fl = 1;
        for (int j = 0; j < 7; j ++) if (s[(i + j) % n] != t[j])fl = 0;
        a[i] = fl; ans += a[i];
    }
    for (int i = n - 6; i <= min(n - 6 + k, 2 * n); i ++)
    {
        int sum = 0;
        for (int j = i; j <= i + 5; j ++)
        {
            int p = (j % n + n) % n;
            sum += a[p];
        }
        // cout << "EEE:" << i << ' ' << sum << endl;
        mn = min(mn, sum);
    }

    cout << ans - mn << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T --) sol();
    return 0;
}
/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
*/