#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;
bool jd(string s){
    if(s.size() < 7) return false;
    return s.substr((int)s.size() - 7) == "nanjing";
}
bool djd(string s){
    if(s.size() < 7) return false;
    return s.substr(0,7) == "nanjing";
}
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";
    }
    
    int sz = ans; 
    for(int i = n,j = 1;i >= 1 && j <= k;--i,++j){
        sz -= jd(str);
        str.pop_back();
        str = t[i] + str;
        sz += djd(str);
        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;
}