#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;


using vi = vector<int>;
using pii = pair<int,int>;

const string t = "nanjing";

void solve() {
	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;

	int res = 0;
	for(int i = 0; i + 6 < n; i ++) 
		if(s.substr(i, 7) == t) res ++;

	for(int i = 1; i <= min(k, 6) and n >= 7; i ++){

		if(s.substr(n - 7 + i, 7 - i) + s.substr(0, i) == t) {
			res ++;
			break;
		}
	}

	cout << res << "\n";
	return;
}

i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T --)
		solve();
	return 0;
}