#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)

constexpr int maxn = 2e5 + 5;
constexpr int mod = 998244353;
int n, k;
string s;

void solve()
{
	cin >> n >> k;
	cin >> s;
	if (n < 7) {cout << 0 << endl; return;}
	s = ' ' + s + s;
	vector<int> a(1 + 2 * n, 0);
	rep(i, 1, 2 * n - 6) if (s.substr(i, 7) == "nanjing") a[i] = 1;
	vector<int> sum(2 * n + 1, 0);
	rep(i, 1, 2 * n - 6) sum[i] = sum[i - 1] + a[i];
	// rep(i, 1, 2 * n) cout << sum[i] << " "; cout << endl;

	if (k >= n) k = n - 1;

	int ans = 0;
	k++;
	rep(i, 1, k) ans = max(ans, sum[i + n - 7] - sum[i - 1]);
	cout << ans << endl;

}

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