Narek 懒得制作本次比赛的第三个问题。他的朋友 Artur 建议他应该使用 ChatGPT。 ChatGPT 会产生 $$$n$$$ 问题,每个问题由 $$$m$$$ 个字母组成,因此 Narek 有 $$$n$$$ 字符串。为了使问题变得更难,他通过选择一些可能没有的 $$$n$$$ 字符串并将它们连接起来而不改变它们的顺序来组合问题。他解决问题的机会定义为 $$$score_n - Score_c$$$,其中 $$$score_n$$$ 是 Narek 的分数,$$$score_c$$$ 是 ChatGPT 的分数。
Narek 通过检查选定的字符串来计算 $$$score_n$$$(他从左向右移动)。他首先搜索字母 $$$\texttt{"n"}$$$,然后搜索 $$$\texttt{"a"}$$$、$$$\texttt{"r"}$$$、$$$\texttt{"e"}$$$ 和 $$$\texttt{"k"}$$$。找到所有出现的这些字母后,他将 $$$score_n$$$ 增加 $$$5$$$ 并再次继续搜索 $$$\texttt{"n"}$$$ (他不会返回,只是从上次停下的地方继续)。
Narek 完成后,ChatGPT 扫描数组,并为每个字母 $$$\texttt{"n"}$$$、$$$\texttt{"a"}$$$、$$$\texttt{"r"}$$$、$$$\texttt{"e"}$$$ 将 $$$score_c$$$ 增加 $$$1$$$,或者Narek 未能利用的 $$$\texttt{"k"}$$$ (请注意,如果 Narek 未能通过找到所有 $$$5$$$ 字母来完成最后一次出现,那么他使用的所有字母都将计入 ChatGPT 的分数 $$$score_c$$$ 中,如果 Narek 没有完成找到所有 5 个字母,则 Narek 不会获得任何分数)。
Narek 的目标是通过选择初始字符串的最优子集来最大化 $$$score_n - Score_c$$$ 的值。
输入
在输入的第一行中,您将获得一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$),即测试用例的数量。然后是每个测试用例的描述。
在每个测试用例的第一行,给出两个整数 $$$n, m$$$ ($$$1 \le n, m \le 10^3$$$)、字符串数量和每个字符串的长度。
在接下来的 $$$n$$$ 行中,您将获得 $$$n$$$ 字符串,每个字符串的长度为 $$$m$$$。字符串仅包含英文字母表中的小写字母。
所有测试用例的 $$$n \cdot m$$$ 值的总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出一个整数:$$$score_n - Score_c$$$ 的最大可能值。
示例
输入 #1
4 5 2 nn aa rr ee kk 1 5 narek 1 4 nare 5 7 nrrarek nrnekan uuuuuuu ppppppp nkarekz
输出 #1
0 5 0 7
注意
在第一个测试用例中,最佳答案之一是 Narek 不选择任何字符串,因此答案是 $$$0$$$。他也可以选择所有字符串。在这种情况下,完整的字符串变为“nnaarreekk”。 Narek 可以选择所有字母的第一次出现并将 $$$5$$$ 添加到分数中。他的对手将为所有第二次出场添加 $$$1$$$,总共为 $$$5$$$。所以答案是 $$$5 - 5 = 0$$$。
在第三个测试用例中,唯一的最佳答案是 Narek 不选择字符串。请注意,如果他要选择字符串,他将无法找到最后一个字母“k”,因此他的分数将保持在 $$$0$$$ 而不是 $$$5$$$。然后 ChatGPT 将为所有 $$$4$$$ 字母添加 $$$4$$$,答案将变为 $$$0 - 4 = -4$$$。
在最后一个测试用例中,Narek 需要选择第一个和最后一个字符串。将这两个放在一起后,他得到“$$${\color{red}{n}}rr{\color{red}{a}}{\color{red}{r}}{\color{red}{e}}{\color{red}{k}}{\color{red}{n}}k{\color{red}{a}}{\color{red}{r}}{\color{red}{e}}{\color{red}{k}}{\color{blue}{z}}$$$”。 Narek 可以选择标有红色的字母,并将 $$$10$$$ 添加到他的分数中。由于 Narek 留下的黑色字母有资格被对手认领(它们用于单词“narek”),因此对手将所有其他字母添加到分数中,并获得 $$$3$$$ 分数。因此,答案是$$$10 - 3 = 7$$$。