#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 50;
const ll mod = 998244353;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数

void work() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    string t = "nanjing";
    int ans = 0;
    for (int i = 0; i + 6 < n; ++i) {
        string x = s.substr(i, 7);
        if (x == t) ans++;
    }
    for (int i = n - 6, j = 1; j <= k && i >= 0 && i < n; ++i, ++j) {
        string x = s.substr(i, n - i) + s.substr(0, j);
        if (x == t) ans++;
    }
    cout << ans << '\n';
}

signed main() {
    io;
    int t = 1;
    cin >> t;
    while (t--) {
        work();
    }
    return 0;
}
/*
4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc
 */