#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int ans = 0;
        for(int i = 0; i <= min(k, 8); i++){
            int cnt = 0;
            for(int j = 0; j < s.size(); j++){
                if (s.substr(j, 7) == "nanjing"){
                    cnt += 1;
                }
            }
            ans = max(ans, cnt);
            rotate(s.begin(), s.begin() + 1, s.end());
        }
        cout << ans << '\n';
    }

}