#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";
    }
    
    // cerr << "ans = " << ans << endl;
    int sz = ans; 
    for(int i = n + 1,j = 1;i <= 2 * n && j <= k;++i,++j){
        sz -= djd(str);
        str.erase(str.begin());
        str = str + t[i];
        sz += jd(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;
}