#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<int , int>;

void solved() {
   int n , k;
   cin >> n >> k;

   string s;
   cin >> s;
   k = min(n , k);

   if(s.size() < 7){
       cout << "0\n";
       return ;
   }


   string s1 = "nanjing";

   for(int i = 0 ; i < k ; i ++ )
       s += s[i];
   int ans = 0;
   for(int i = 0 ; i + 7 <= n ; i ++ ){
       string a = s.substr(i , 7);
       if(a == s1) ans ++;
   }

   int res = ans;
   for(int i = n - 6 ; i + 7 <= s.size() ; i ++ ){
       string a = s.substr(i , 7);
       if(a == s1) ans ++;
       a = s.substr(i - n + 6 ,  7);
       if(a == s1) ans --;
       res = max(res , ans);
   }

   cout << res << "\n";
}

int main(){

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

    int t = 1;
    cin >> t;

    while(t -- )
        solved();

    return 0;
}