#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int MAX = 3e5 + 5;

void solve(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int ans = 0;
    string t = "nanjing";
    for (int i = 0; i < min(7, k + 1); i ++){
        int cur = 0, res = 0;
        for (int j = 0; j < n; j ++){
            if (s[(i + j) % n] == t[cur]){
                cur ++;
                if (cur == 7){
                    res ++;
                    cur = 0;
                }
            }
            else cur = 0;
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // cout << fixed << setprecision(10);
    int T;cin>>T;while (T--)
        solve();
}