#include<bits/stdc++.h>
// #define int long long
#define eb emplace_back
#define mp make_pair
#define DEBUG
using namespace std;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using piiii = pair<pii, pii>;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int P = 998244353;const i64 inf = 0x3f3f3f3f3f3f3f3f;
namespace azus{
	int n, k;
	string s;
	int check(int l, int r){
		int ret = 0;
		for(int i = l; i + 6 <= r; i ++){
			string x = "";
			for(int j = i; j <= i + 6; j ++)
				x += s[j];
			// cout << x << "\n";
			if(x == "nanjing") ret ++;
		}
		return ret;
	}
	int main(){
		cin >> n >> k;
		cin >> s; 
		s = s + s;
		s = " " + s;
		int ans = 0;
		for(int i = 1; i <= min(k + 1, 8) && i <= n; i ++){
			ans = max(ans, check(i, i + n - 1));
		}
		cout << ans << "\n";
		return 0;
	}
}
signed main(){
#ifndef DEBUG
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#endif
	int T = 1;
	cin >> T;
	while(T --)
		azus::main();
	return 0;
}