这是 Codeforces Round #1797 的一道题“C. Lazy Narek”。我将其翻译成中文，并按要求在数字和公式前后加上 $ 符号，同时重新排版。

---

C. 懒惰的 Narek

每测试点时间限制：$2$ 秒
每测试点内存限制：$256$ MB

Narek 太懒了，不想创建这场比赛的第三道题目。他的朋友 Artur 建议他使用 ChatGPT。ChatGPT 生成了 $n$ 道题目，每道题目由 $m$ 个字母组成，因此 Narek 有 $n$ 个字符串。

为了让题目更难，他通过选择其中一些字符串（可能一个也不选），并按原顺序将它们拼接起来。他解题的得分定义为 $\text{score}_n - \text{score}_c$，其中 $\text{score}_n$ 是 Narek 的得分，$\text{score}_c$ 是 ChatGPT 的得分。

Narek 通过扫描选中的字符串（从左到右）来计算 $\text{score}_n$。他一开始搜索字母 "n"，然后是 "a"，"r"，"e"，"k"。当他找到所有这些字母的连续出现后，他将 $\text{score}_n$ 增加 $5$，并重新开始搜索 "n"（他不会回溯，而是从他停下的地方继续）。

Narek 完成后，ChatGPT 扫描整个字符串，对于每个 Narek 未能利用的字母 "n"、"a"、"r"、"e" 或 "k"，将 $\text{score}_c$ 增加 $1$（注意：如果 Narek 未能通过找到所有 $5$ 个字母来完成最后一次出现，那么他使用的所有字母都会计入 ChatGPT 的得分 $\text{score}_c$，并且如果他没有完成找到所有 $5$ 个字母，则 Narek 得不到任何分数）。

Narek 的目标是通过选择最优的初始字符串子集，最大化 $\text{score}_n - \text{score}_c$ 的值。

---

输入

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \le n, m \le 10^3$），分别表示字符串的数量和每个字符串的长度。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串。这些字符串只包含英文字母的小写字母。

所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

---

输出

对于每个测试用例，输出一个整数：$\text{score}_n - \text{score}_c$ 的最大可能值。

---

示例

输入

4
5 2
nn
aa
rr
ee
kk
1 5
narek
1 4
nare
5 7
nrrarek
nrnekan
uuuuuuu
ppppppp
nkarekz

输出

0
5
0
7

---

提示

在第一个测试用例中，最优解之一是 Narek 不选择任何字符串，因此答案为 $0$。他也可以选择所有字符串。在这种情况下，完整的字符串变为 "nnaarreekk"。Narek 可以选择所有字母的第一次出现并增加 $5$ 分。他的对手将为所有第二次出现增加 $1$ 分，总共 $5$ 分。因此答案为 $5 - 5 = 0$。

在第三个测试用例中，唯一的最优解是 Narek 不选择该字符串。注意，如果他选择该字符串，他将无法找到最后一个字母 "k"，因此他的得分仍为 $0$，而不是 $5$。然后 ChatGPT 会为 $4$ 个字母各加 $1$ 分，答案变为 $0 - 4 = -4$。

在最后一个测试用例中，Narek 需要选择第一个和最后一个字符串。将这两个字符串拼接后得到 "nrrareknkarekz"。Narek 可以选择红色标记的字母并增加 $10$ 分。由于 Narek 留下的黑色字母符合对手认领的条件（它们被用于单词 "narek" 中），对手将所有其他字母加入得分，得到 $3$ 分。因此答案为 $10 - 3 = 7$。

---

如果你需要该题的解题思路或代码实现，我可以继续提供。