#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ld long double
using namespace std;
int dx[] = { -1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };
const int NC = 2e3 + 10;
char ches[NC][NC];
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N], b[N], n, m,k;
void solve() {
    //注意审题吧
    cin >> n >> k;
    k = min(k,n);
	string s; cin >> s;
    
    string t = ' ' + s + s + ' ';
    
    string str = s;
    int ans = 0;
    for(int i = 0;i + 6 < s.size();++i){
        ans += s.substr(i,7) == "nanjing";
    }
    
    auto jd = [&](int l,int r) ->bool{
        if(r - l + 1 < 7) return false;
        return t[r - 6] == 'n' && t[r - 5] == 'a' && t[r - 4] == 'n' && 
                t[r - 3] == 'j' && t[r - 2] == 'i' && t[r - 1] == 'n' && t[r] == 'g';  
    };
    
    auto djd = [&](int l,int r) ->bool{
        if(r - l + 1 < 7) return false;
        return t[l] == 'n' && t[l + 1] == 'a' && t[l + 2] == 'n' && 
                t[l + 3] == 'j' && t[l + 4] == 'i' && t[l + 5] == 'n' && t[l + 6] == 'g';  
    };
    
    // cerr << "ans = " << ans << endl;
    int sz = ans; 
    for(int i = n + 1,j = 1;i <= 2 * n && j <= k;++i,++j){
        sz -= djd(i - n + 1,i);
        sz += jd(i - n + 1,i);
        ans = max(ans,sz);
    }
    
    cout << ans << endl;
}
signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1; 
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}