#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

ll cal(const string& str , int s){
   ll ans = 0;
   for (int i = s ; i < str.size() ; i++){
       if (str.substr(i , 7) == "nanjing") ans++;
   }
   return ans;
}

void slove() {
    int n, k;
    cin >> n >> k;
    k = min(n, k);

    string str;
    cin >> str;

    k = min(k , 7);
    

    ll ans = 0;
    for (int i = 0 ; i <= k ; i++){
        ans = max(ans , cal(str , i));
        str.push_back(str[i]);
        // str.erase(str.begin());
    }

    cout << ans << endl;

    // if (str.size() >= 7) {
    //     for (int i = 0; i < 6; i++) {
    //         str.push_back(str[i]);
    //     }
    // }

    // vector<int> in(str.size(), 0);

    // int cnt = 0;
    // for (int i = 0; i + 6 < str.size(); i++) {
    //     if (str.substr(i, 7) == "nanjing") {
    //         cnt++;
    //         for (int j = 1; j < 6; j++) in[i + j] = 1;
    //     }
    // }

    // if (str.size() >= 7) {
    //     for (int i = 0; i < 6; i++) {
    //         in[i] = in[str.size() - 6 + i];
    //     }
    // }

    // for (int i = 0; i <= k; i++) {
    //     if (!in[i]) {
    //         cout << cnt << "\n";
    //         return;
    //     }
    // }
    // cout << (cnt - 1) << "\n";
    return;
}

int main() {
    // freopen("in.txt" , "r" , stdin);
    int cnt = 1;
    cin >> cnt;

    while (cnt--) {
        slove();
    }
}