#include<bits/stdc++.h>
typedef long long ll;
int f[(int)4e5 + 1000];
void solve(){
    int n,k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;
    s += s;
    // std::fill(f + 1,f + 1 + (n << 1),0);
    int n2 = s.size();
    std::fill(f + 1,f + 1 + n2,0);
    for(int i = 0;(i + 7) < n2;i++){
        if(s.substr(i,7) == "nanjing"){
            f[i + 1]++;
        }
        f[i + 1] += f[i];
    }
    int ans = 0;
    // for(int i = 0;i <= n2;i ++){
    //     std::cout << f[i] << " ";
    // }
    // std::cout << "\n";
    for(int i = 0;i < n and i <= k;i++){
        int tmp = f[i + n] - f[i];
        // j - l + 1 == 6
        // l = i + n - 6
        for(int j = i + n - 1;j >= i + n - 6 and j >= 0;j--){
            if((j + 7) < n2 and s.substr(j,7) == "nanjing"){
                tmp--;
            }
        }
        ans = std::max(ans,tmp);
        // ans = std::max(ans,f[i + n] - f[i]);
    }
    std::cout << ans << "\n";
}
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0),std::cout.tie(0);
    int t;
    std::cin >> t;
    while(t--){
        solve();
    }
    return 0;
}