#include <bits/stdc++.h>
using namespace std;

const string target = "nanjing";
const int target_length = target.length();

int countNanjingOccurrences(const string &s) {
    int count = 0;
    size_t pos = s.find(target);
    while (pos != string::npos) {
        count++;
        pos = s.find(target, pos + 1);
    }
    return count;
}

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

    int T;
    cin >> T;

    while (T--) {
        long long n, k;
        cin >> n >> k;
        string s;
        cin >> s;

        // 1. 原始字符串中的出现次数
        int maxCount = countNanjingOccurrences(s);
        
        // 2. 形成一个循环字符串
        string doubledS = s + s;
        
        // 3. 计算位置
        vector<int> prefix_count(n * 2 + 1, 0);
        
        // 4. 记录在 doubledS 中 "nanjing" 出现的位置
        for (int i = 0; i <= n; ++i) {
            if (doubledS.substr(i, target_length) == target) {
                prefix_count[i] = 1;
            }
        }
        
        // 5. 计算前缀和，方便后续查询
        for (int i = 1; i < prefix_count.size(); ++i) {
            prefix_count[i] += prefix_count[i - 1];
        }

        // 6. 通过循环的位置查找最多出现的数量
        int maxShift = min(n, k);
        for (int d = 0; d <= maxShift; ++d) {
            int start = d;
            int end = d + n - 1;
            int currentCount = prefix_count[end + 1] - prefix_count[start]; // 计算在区间内的“nanjing”出现次数
            maxCount = max(maxCount, currentCount);
        }

        cout << maxCount << '\n';
    }

    return 0;
}