#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define all(a) a.begin(),a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0;}
bool chmax(auto& a, auto b) {return a < b ? a = b, 1 : 0;}

void solve(){
	ll n,k; cin >> n >> k;
	string s; cin >> s;
	vl sum(2*n+1);
	string t = "nanjing";
	ll m = t.size();
	s += s;
	ll ans = 0;
	rep(i,n){
		bool flag = true;
		rep(j,m){
			if(s[i+j] != t[j]) flag = false;
		}
		if(!flag) continue;
		ans++;
		ll now = i;
		rep2(i,now-n+1,now-n+m){
			if(0 <= i && i <= 2*n) sum[i]++;
		}
		while(true){
			if(now >= 2*n) break;
			ll r = now+m;
			rep2(i,now+1,min(r,2*n+1)) sum[i]++;
			now += n;
		}
	}
	//rep(i,2*n+1) cout << sum[i] << " ";
	//cout << endl;
	ll mi = ans;
	rep(i,min(k+1,2*n+1)) chmin(mi, sum[i]);
	cout << ans-mi << "\n";
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	ll T; cin >> T;
	while(T--) solve();
}