#include <bits/stdc++.h>

using LL = long long;

constexpr int inf = 1E9;

void solve()
{
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    const std::string t = "nanjing";

    int ans = 0;

    for (int i = std::min(6, k); i > 0 && n - i >= 0; i--)
    {
        if (s.substr(n - i) == t.substr(0, i) && s.substr(0, 7 - i) == t.substr(i))
        {
            ans++;
            break;
        }
    }

    for (int i = 0; i + 7 <= n; i++)
    {
        ans += s.substr(i, 7) == t;
    }

    std::cout << ans << '\n';
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;

    while (T--)
    {
        solve();
    }

    return 0;
}