#include<bits/stdc++.h>
#define rep(i, j ,k) for(int i = (j); i <= (k); ++i)
#define dep(i, j, k) for(int i = (j); i >= (k); --i)
using i64 = int64_t;
using f64 = double_t;
#define pb push_back
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define maxn 100005
using namespace std;

int T;

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if(s.find("nanjing") == string::npos) {
        int t = min(7, k);
        rep(i, 1, t) {
            char c = s[0];
            s.erase(0, 1);
            s.push_back(c);
            if(s.find("nanjing") != string::npos) {
                cout << 1 << endl;
                return;
            }
        }
        cout << 0 << endl;
    }else {
        int idx = s.find("nanjing");
        int len = min(idx, k);
        string p = s.substr(0, len);
        s.erase(0, len);
        s.append(p);
        int ans = 0;
        while (s.find("nanjing") != string::npos) {
            int id = s.find("nanjing");
            s.erase(0, id + 7);
            ans++;
        }
        cout << ans << endl;
    }
}

int main () {
    ios:: sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    T = 1;
    cin >> T;
    while(T--) solve();
}