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

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

    string str;
    cin >> str;

    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 < 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();
    }
}