C. Лентяй Нарек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нареку лень придумывать третью задачу этого контеста, поэтому его друг Артур предложил использовать ChatGPT. ChatGPT сгенерировал $$$n$$$ задач, каждая из которых состоит из $$$m$$$ букв, и Нарек рассматривает их как $$$n$$$ строк. Чтобы усложнить задачу, он комбинирует задачи, выбирая некоторые из $$$n$$$ строк (возможно, ни одной) и располагая их без изменения порядка. Его шанс решить задачу определяется как $$$score_n - score_c$$$, где $$$score_n$$$ — счёт Нарека, а $$$score_c$$$ — счёт ChatGPT.

Нарек вычисляет $$$score_n$$$, изучая выбранную строку (он двигается слева направо). Изначально он ищет букву $$$\texttt{«n»}$$$, после неё буквы $$$\texttt{«a»}$$$, $$$\texttt{«r»}$$$, $$$\texttt{«e»}$$$ и $$$\texttt{«k»}$$$. Найдя все вхождения этих букв, он увеличивает $$$score_n$$$ на $$$5$$$ и возобновляет поиск $$$\texttt{«n»}$$$ (он не возвращается назад, а просто продолжает с того места, на котором остановился).

После того как Нарек закончит, ChatGPT просматривает строку и увеличивает $$$score_c$$$ на $$$1$$$ для каждой буквы $$$\texttt{«n»}$$$, $$$\texttt{«a»}$$$, $$$\texttt{«r»}$$$, $$$\texttt{«e»}$$$, или $$$\texttt{«k»}$$$, которые Нарек не смог использовать. Обратите внимание, что если Нарек не смог завершить последнее вхождение, найдя все $$$5$$$ букв, то использованные им буквы учитываются в счёте ChatGPT $$$score_c$$$, а Нарек не получает никаких очков, если он не закончил поиск всех 5 букв.

Помогите Нареку максимизировать значение $$$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$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных один из оптимальных ответов — когда Нарек не выбирает ни одну из строк, поэтому ответ равен $$$0$$$. В качестве альтернативы он может выбрать все строки. В этом случае полная строка становится «nnaarreekk». Нарек может выбрать первые появления всех букв и добавить к счету $$$5$$$. Его соперник добавит по $$$1$$$ за все вторые появления, что в сумме составит $$$5$$$. Поэтому ответ будет $$$5 - 5 = 0$$$.

В третьем наборе входных данных единственный оптимальный ответ — когда Нарек не выбирает строку. Обратите внимание, что если бы он выбрал строку, то не смог бы найти последнюю букву «k», поэтому его счёт остался бы на уровне $$$0$$$, а не стал бы $$$5$$$. Затем ChatGPT добавил бы $$$4$$$ за $$$4$$$ буквы, и разница счётов стала бы $$$0 - 4 = -4$$$.

В последнем наборе входных данных Нареку нужно выбрать первую и последнюю строки. Поместив эти две строки рядом друг с другом, он получает «$$${\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}}$$$». Нарек может выбрать буквы, отмеченные красным цветом, и добавить к своему счету $$$10$$$. Так как буквы чёрного цвета, которые оставил Нарек, может забрать соперник (они используются в слове «Нарек»), то он прибавляет к счету все остальные буквы и получает счет $$$3$$$. Таким образом, ответ составляет $$$10 - 3 = 7$$$.