#include <bits/stdc++.h>

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

    std::string S, s = " nanjing ";
    std::cin >> S;

    int ans = 0;
    for (int k = 0; k <= std::min(7, std::min(n - 1, m)); k++) {
        std::string t = S.substr(k) + S.substr(0, k);
        // std::cout << t << '\n';
        t = ' ' + t;
        std::vector<int> next(7 + 1, 0);
        std::vector<int> f(n + 1, 0);
        for (int i = 2, j = 0; i <= 7; i++) {
            while (j > 0 && s[j + 1] != s[i]) j = next[j];
            if (s[j + 1] == s[i]) j++;
            next[i] = j;
        }
        int cnt = 0;
        for (int i = 1, j = 0; i <= n; i++) {
            while (j > 0 && (j == 7 || s[j + 1] != t[i])) j = next[j];
            if (s[j + 1] == t[i]) j++;
            f[i] = j;
            if (f[i] == 7) cnt++;
        }
        ans = std::max(ans, cnt);
    }
    
    std::cout << ans << '\n';

}

int main() {
    int T;
    std::cin >> T;

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