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

typedef long long ll;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


int L, K;
string s;

void exe() {
    cin >> L >> K >> s;

    vector<bool> yes(L, true);
    for (int i=0; i<L; i++) {
        for (int j=0; j<7; j++) yes[i] = yes[i] && (s[(i+j)%L] == ("nanjing"[j]));
    }

    int sum = 0;
    for (int i=0; i<L; i++) sum += yes[i];

    K = min(K, L);

    int ans = 0;
    for (int i=0; i<=K; i++) {
        int now = sum;
        for (int j=L-6; j<L; j++) now -= yes[(i+j)%L];

        ans = max(ans, now);
    }

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


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int tc;
    cin >> tc;

    for (int i=1; i<=tc; i++) exe();
}