#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (n < 7)
        return cout << "0" << endl, void();
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (i + 6 < n)
        {
            string tmp = s.substr(i, 7);
            if (tmp == "nanjing")
                cnt++;
        }
    }
    for (int i = 1; i <= min(k, 6); i++)
    {
        int p = 7 - i;
        string t1 = s.substr(n - p, p), t2 = s.substr(0, i);
        string tmp = t1 + t2;
        if (tmp == "nanjing")
        {
            cnt++;
            break;
        }
    }
    cout << cnt << endl;
}
signed main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}