#include<bits/stdc++.h>

using ll=long long;

void work()
{
    int n,k;
    std::cin>>n>>k;
    std::string t;
    std::cin>>t;
    int ans=0;
    for(int i=0;i<=std::min(7,k);i++)
    {
        //std::cout<<t<<'\n';
        int sum=0;
        for(int j=0;j<t.size();j++)
        {
            if(j+6<t.size()&&t[j]=='n'&&t[j+1]=='a'
            &&t[j+2]=='n'&&t[j+3]=='j'&&t[j+4]=='i'&&t[j+5]=='n'&&t[j+6]=='g') sum++;
        }
        ans=std::max(ans,sum);
        std::rotate(t.begin(),t.begin()+1,t.end());
    }
    std::cout<<ans<<'\n';
}
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(0);
    int t=1;
    std::cin>>t;
    while(t--)
        work();
    return 0;
}