#include<bits/stdc++.h>
using namespace std;
#define db(x) cerr<<#x<<(x)<<" \n"
#define ll long long
void solve(){
    int n,k;
    string s;cin>>n>>k>>s;
    string t1 = "nanjing",t2 = "nan",t3 = "jing";
    auto ok= [&](string t){
        int ans =0,idx =0,m = t.size();
        while(1){
            idx =s.find(t,idx);
            if(idx==-1)break;
            ans++;
            idx+=m;
        }
        return ans;
    };
    int num1= ok(t1),num2 =ok(t2),num3 = ok(t3);
    num2-=num1;num3-=num1;
    if(s.size()<6){
        cout<<"0\n";return ;
    }
    if(s.substr(0,4)==t3){
        ++k;
    }
 //   db(num2),db(num3);db(num1);
    int res = num1+min(min(num2,num3),k/2);
    cout<<res<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)solve();
    return 0;
}