#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 计算字符串哈希值的函数（简单的多项式哈希示例）
const int p = 31;
const int m = 1e9 + 9;
vector<long long> p_pow;
// 预处理p的幂
void precompute_pow(int n) {
p_pow.resize(n);
p_pow[0] = 1;
for (int i = 1; i < n; i++) {
p_pow[i] = (p_pow[i - 1] * p) % m;
}
}
// 计算字符串的哈希值
vector<long long> compute_hash(const string& s) {
int n = s.length();
vector<long long> h(n + 1);
h[0] = 0;
for (int i = 0; i < n; i++) {
h[i + 1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
}
return h;
}
// 获取子串的哈希值
long long get_hash(const vector<long long>& h, const int& l, const int& r, const vector<long long>& p_pow) {
long long res = h[r + 1] - h[l];
res = (res + m) % m;
res = (res * p_pow[n - r - 1]) % m;
return res;
}
int main() {
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
precompute_pow(n);
// 计算“nanjing”的哈希值
string target = "nanjing";
vector<long long> target_hash = compute_hash(target);
int target_val = target_hash.back();
int max_count = 0;
for (int d = 0; d <= k; d++) {
string shifted_s = s.substr(d) + s.substr(0, d);
vector<long long> shifted_hash = compute_hash(shifted_s);
int count = 0;
int len = shifted_s.length();
for (int l = 0; l < len; l++) {
for (int r = l; r < len; r++) {
long long sub_hash = get_hash(shifted_hash, l, r, p_pow);
if (sub_hash == target_val) {
count++;
}
}
}
if (count > max_count) {
max_count = count;
}
}
cout << max_count << endl;
}
return 0;
}