#include<bits/stdc++.h>
#define int long long
#define MAXN 300005
#define INf 2147483647
#define fn(i,st,ed) for(int i=st;i<=ed;i++)
#define fd(i,st,ed) for(int i=st;i>=ed;i--)
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void solve(){
    int n,k,ans=0;cin>>n>>k;
    string s;cin>>s;
    s=s+s;
    int cnt=0;
    fn(i,0,2*n-7){
        //cout<<s.substr(i,7)<<endl;
        if(s.substr(i,7)=="nanjing")cnt++;
        //cout<<cnt<<endl;
    }
    ans+=((n+k)/(n*2))*cnt;
    //cout<<n<<' '<<k<<endl;
    int now=(k+n)%(n*2);
    //cout<<"now:"<<now<<endl;
    fn(i,0,now-7){
        //cout<<s.substr(i,7)<<endl;
        if(s.substr(i,7)=="nanjing")ans++;
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){solve();}
    return 0;
}