#include <bits/stdc++.h>

using namespace std;

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

	string s;
	cin >> s;

	s = s + s;

	int cnt = 0;

	string nanjing = "nanjing";

	//cout << s << endl;

	if(n <= 6) {
		cout << "0\n";
		return;
	}

	int last = n + min(k, 6);

	for(int i = 0; i < last; i ++) {
		//cout << i << ' ';
		if(s[i] == 'n' && i + 6 < last) {
			//cout << i << ' ';
			bool flag = 0;
			for(int j = i; j < 7; j ++) {
			//	cout << "what";
				if(s[j] == nanjing[j - i]) continue;
				else {
					flag = 1;
					break;
				}
			}
			if(flag == 0) {
				//cout << i << ' ';
				cnt ++;
			}
		}
	}

	cout << cnt << '\n';
}

int main()
{
	int t;
	cin >> t;

	while(t--)
		solve();

	return 0;
}