#include<bits/stdc++.h>
using namespace std;
char s[400005];
void sol()
{
    int n,k;
    cin>>n>>k;
    if(k>n)k=n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    if(n<7)
    {
        cout<<"0\n";
        return;
    }
    for(int i=1;i<=k;i++)
        s[i+n]=s[i];
    int now=0;
    for(int i=1;i<=n-6;i++)
    {
        if(s[i]=='n'&&s[i+1]=='a'&&s[i+2]=='n'&&s[i+3]=='j'&&s[i+4]=='i'&&s[i+5]=='n'&&s[i+6]=='g')
            now++;
    }
    int mx=now;
    for(int i=n+1;i<=n+k;i++)
    {
        if(s[i-n]=='n'&&s[i-n+1]=='a'&&s[i-n+2]=='n'&&s[i-n+3]=='j'&&s[i-n+4]=='i'&&s[i-n+5]=='n'&&s[i-n+6]=='g')
            now--;
        if(s[i-6]=='n'&&s[i-5]=='a'&&s[i-4]=='n'&&s[i-3]=='j'&&s[i-2]=='i'&&s[i-1]=='n'&&s[i]=='g')
            now++;
        mx=max(now,mx);
    }
    cout<<mx<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
        sol();
}