P14018 [ICPC 2024 Nanjing R] Left Shifting 3

Given a string $S = s_0s_1\cdots s_{n-1}$ of length $n$, you can shift $S$ to the left for at most $k$ times (including zero times). Calculate the maximum number of ``nanjing`` substrings contained in the string after the operations. More formally, let $f(S, d)$ be the string obtained by shifting $S$ to the left $d$ times. That is, $f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}$. Let $g(f(S, d), l, r) = s_{(d+l)\bmod n}s_{(d+l+1)\bmod n}\cdots s_{(d+r)\bmod n}$. Let $h(d)$ be the number of integer pairs $(l, r)$ such that $0 \le l \le r < n$ and $g(f(S, d), l, r) =$ \texttt{nanjing}. Find an integer $d$ such that $0 \le d \le k$ to maximize $h(d)$ and output this maximized value.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \times 10^5$, $0 \le k \le 10^9$) indicating the length of the string and the maximum number of left shifts you can perform. The second line contains a string $s_0s_1\cdots s_{n - 1}$ of length $n$. The string consists of lower-cased English letters. It's guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$.

For each test case, output one line containing one integer, indicating the maximum number of ``nanjing`` substrings contained in the string.

对于第一组样例数据，我们可以将字符串左移 $6$ 次，得到字符串 ``pcnanjingsuananjingic``。其中有两个 ``nanjing`` 子串。 对于第二组样例数据，因为 $k = 0$，我们无法进行任何左移操作。原字符串中有一个 ``nanjing`` 子串。