#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, INF = 1e18, MOD = 1e9 + 7;
typedef pair<int, int> PII;
typedef unsigned long long ull;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int arr[N], brr[N];
bool st[N];
int n, m, k;

void solve()
{
	cin >> n >> m;
	string s, b = "nanjing";
	cin >> s;
	string t = s + s;
	vector<int> ans;
	int cnt = 0, f;
	for(int i = 0; i < (int)t.size(); i ++){
		string w = t.substr(i,7);
		if(w == b) {
			if(!cnt)f = i;
			cnt ++;
			ans.push_back(i + 6);
		}
	}
	int k = min(m, f);
	for(int i = 0; i < (int)ans.size(); i ++){
		if(ans[i] < (int)s.size()) continue;
		if(ans[i] - (int)s.size() <= k) continue;
		else cnt --;
	}
	cout << cnt << "\n";
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T --)	solve();
	return 0;
}