#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> PII;
#define endl '\n'
const int N=1e6+10;
const int mod=1e9+7;
const double eps=1e-9;
ll a[1010][1010];
vector<PII> v;
bool check1(int mid, ll l){
    if(v[mid].first >= l)return true;
    else return false;
}
bool check2(int mid, ll r){
    if(v[mid].second <= r)return true;
    else return false;
}
void solve()
{
    v.clear();
    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s+=s.substr(0,min(n,k));
    s=' '+s;
    ll m=s.size()-1;
    int ans=0;
    for(int i=1;i+6<=m;i++)
    {
        string t=s.substr(i,7);
        if(t=="nanjing") 
        {
            ans++;
            i+=6;
            v.push_back({i, i + 6});
        }
    }
    if(v.size() == 0){
        cout << 0 << endl;
        return;
    }
    for(int i = 1; i + n - 1 <= m; i ++ ){
        int nl = i, nr = i + n - 1;
        int l = 0, r = v.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(check1(mid, nl)) r = mid;
            else l = mid + 1;
        }
        if(check1(l, nl) == false)continue;
        int c1 = l;
        l = 0, r = v.size() - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(check2(mid, nr)) l = mid;
            else r = mid - 1;
        }
        int c2 = l;
        ans = max(ans, max(0, c2 - c1 + 1));
    }
    cout << ans << endl;   
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)
    {
        solve();    
    }    
    return 0;
}