#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 计算字符串哈希值的函数（简单的多项式哈希示例）
const int p = 31;
const int m = 1e9 + 9;
vector<long long> p_pow;

// 预处理p的幂
void precompute_pow(int n) {
    p_pow.resize(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++) {
        p_pow[i] = (p_pow[i - 1] * p) % m;
    }
}

// 计算字符串的哈希值
vector<long long> compute_hash(const string& s) {
    int n = s.length();
    vector<long long> h(n + 1);
    h[0] = 0;
    for (int i = 0; i < n; i++) {
        h[i + 1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
    }
    return h;
}

// 获取子串的哈希值
long long get_hash(const vector<long long>& h, const int& l, const int& r, const vector<long long>& p_pow) {
    long long res = h[r + 1] - h[l];
    res = (res + m) % m;
    res = (res * p_pow[n - r - 1]) % m;
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        precompute_pow(n);
        // 计算“nanjing”的哈希值
        string target = "nanjing";
        vector<long long> target_hash = compute_hash(target);
        int target_val = target_hash.back();
        int max_count = 0;
        for (int d = 0; d <= k; d++) {
            string shifted_s = s.substr(d) + s.substr(0, d);
            vector<long long> shifted_hash = compute_hash(shifted_s);
            int count = 0;
            int len = shifted_s.length();
            for (int l = 0; l < len; l++) {
                for (int r = l; r < len; r++) {
                    long long sub_hash = get_hash(shifted_hash, l, r, p_pow);
                    if (sub_hash == target_val) {
                        count++;
                    }
                }
            }
            if (count > max_count) {
                max_count = count;
            }
        }
        cout << max_count << endl;
    }
    return 0;
}

answer.code: In function ‘long long int get_hash(const std::vector<long long int>&, const int&, const int&, const std::vector<long long int>&)’:
answer.code:35:24: error: ‘n’ was not declared in this scope
   35 |     res = (res * p_pow[n - r - 1]) % m;
      |                        ^