#include<bits/stdc++.h>
using namespace std;

int main(){
	int t;
	cin >> t;
	while(t--){
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;
		int ans = 0;
		for(int i = 0; i < min(10, k+1); ++i){
			int cnt = 0;
			for(int j = 0; j < n-6; ++j){
				if(s.substr(j, 7) == "nanjing") ++cnt;
			}
			ans = max(ans, cnt);
			string t = "";
			for(int j = 1; j < n; ++j){
				t += s[j];
			}
			t += s[0];
			s = t;
		}
		cout << ans << endl;
	}
	return 0;
}