#include<bits/stdc++.h>
#define fu(i, l, r) for(int i = l; i <= r; ++i)
#define FU(i, l, r) for(ll  i = l; i <= r; ++i)
#define re(i, l, r) for(int i = r; i >= l; --i)
#define RE(i, l, r) for(ll  i = r; i >= l; --i)
#define setpre(x) fixed << setprecision(x)
#define var auto
#define endl "\n"
#define fi first
#define se second
#define pii  pair<int, int>
#define pll  pair<ll, ll>
#define vi   vector<int>
#define vl   vector<ll>
#define vvi  vector<vector<int>>
#define vvl  vector<vector<ll>>
#define pq   priority_queue
#define eb   emplace_back
#define all(x, t) x.begin() + t, x.end()
#define Nanako7_ix 0
using ll = long long;
using namespace std;
const ll maxn = 1000005;
const ll Mod = 998244353;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3fffffffff;
const long double pi = acosl(-1.0);

void solve() {
    int n, k, ans = 0;
    string s;
    cin >> n >> k >> s;
    if(n < 7) {
        cout << 0 << endl;
        return;
    }
    s = ' ' + s;
    fu(i, 1, n - 6) {
        if(s.substr(i, 7) == "nanjing") {
            ans++;
        }
    }

    if(s.substr(1, 1) == "g" && s.substr(n - 5, 6) == "nanjin" && k >= 1) ans++;
    if(s.substr(1, 2) == "ng" && s.substr(n - 4, 5) == "nanji" && k >= 2) ans++;
    if(s.substr(1, 3) == "ing" && s.substr(n - 5, 4) == "nanj" && k >= 3) ans++;
    if(s.substr(1, 4) == "jing" && s.substr(n - 2, 3) == "nan" && k >= 4) ans++;
    if(s.substr(1, 5) == "njing" && s.substr(n - 1, 2) == "na" && k >= 5) ans++;
    if(s.substr(1, 6) == "anjing" && s.substr(n - 0, 1) == "n" && k >= 6) ans++;

    cout << ans << endl;
}

signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    int T = 1;
    cin >> T;
    while(T--) solve();
    return Nanako7_ix;
}