题目描述

给定一个长度为 $n$ 的字符串 $S = s_0s_1\cdots s_{n-1}$，您可以将 $S$ 左移至多 $k$ 次（包括零次）。求操作之后，字符串中最多含有几个 nanjing 子串。

更正式地，令 $f(S, d)$ 表示将 $S$ 左移 $d$ 次后获得的字符串。也就是说 $f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}$。令 $g(f(S, d), l, r) = s_{(d+l)\bmod n}s_{(d+l+1)\bmod n}\cdots s_{(d+r)\bmod n}$。令 $h(d)$ 表示整数对 $(l, r)$ 的数量，满足 $0 \le l \le r < n$ 且 $g(f(S, d), l, r) = \texttt{nanjing}$。找到一个整数 $d$ 满足 $0 \le d \le k$ 并最大化 $h(d)$。输出这个最大化的值。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^5$，$0 \le k \le 10^9$），表示字符串的长度和最多能进行几次左移操作。

第二行输入一个长度为 $n$ 的字符串 $s_0s_1\cdots s_{n - 1}$。字符串由小写英文字母组成。

保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

输出格式

每组数据输出一行一个整数，表示字符串中最多含有几个 nanjing 子串。

4
21 10
jingicpcnanjingsuanan
21 0
jingicpcnanjingsuanan
21 3
nanjingnanjingnanjing
4 100
icpc

2
1
3
0

提示

对于第一组样例数据，我们可以将字符串左移 $6$ 次，得到字符串 pcnanjingsuananjingic。其中有两个 nanjing 子串。

对于第二组样例数据，因为 $k = 0$，我们无法进行任何左移操作。原字符串中有一个 nanjing 子串。