A. Политика
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Клуб дебатов с $$$n$$$ участниками, включая вас (участник $$$1$$$), сегодня последовательно обсудит $$$k$$$ мнений. Во время каждого обсуждения участники выразят свое согласие или несогласие с мнением. Обозначим количество участников, которые согласны, как $$$Y$$$, а количество участников, которые не согласны, как $$$N$$$. После каждого обсуждения участники покидают клуб в соответствии со следующими правилами:

  • Если больше участников согласны с мнением, чем не согласны ($$$Y > N$$$), все участники, которые не согласны, покидают клуб.
  • Если больше участников не согласны с мнением, чем согласны ($$$Y < N$$$), все участники, которые согласны, покидают клуб.
  • В случае ничьей ($$$Y = N$$$), все участники покидают клуб.

Как президент клуба, вы хотите остаться в клубе и максимизировать количество участников, оставшихся после встречи. Вы знаете позицию каждого участника по всем $$$k$$$ мнениям до начала встречи, и вы можете исключить любых участников (кроме себя самого) перед началом встречи.

Определите максимальное количество участников, включая вас, которые могут остаться в клубе после встречи, при условии, что вы также останетесь в клубе после встречи.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 100$$$) — количество участников и количество обсуждений.

$$$i$$$-я из следующих $$$n$$$ строк содержит строку $$$t_i$$$ длины $$$k$$$. $$$j$$$-й символ в строке $$$t_i$$$ указывает, согласится ли $$$i$$$-й участник или не согласится с $$$j$$$-м мнением, если он будет присутствовать во время его обсуждения. Символ «+» означает, что участник согласен, а символ «-» означает, что участник не согласен.

Гарантируется, что сумма значений $$$n \cdot k$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^4$$$.

Выходные данные

Для каждого набора входных данных выведите максимальное количество участников, включая вас, которые могут остаться в клубе после встречи.

Пример
Входные данные
5
2 2
++
+-
1 3
+-+
4 1
+
-
-
+
5 4
++++
+--+
++-+
+-++
++++
4 2
++
--
--
-+
Выходные данные
1
1
2
2
1
Примечание

Для удобства, в примерах ниже мы будем разбирать ситуации, опираясь на то, кто пришел на встречу (т. е. не был исключен перед ней), а не на то, кто был исключён.

Пример 1:

На встречу мог прийти только первый участник, иначе оба участника ушли бы после обсуждения второго мнения.

Пример 2:

На встречу приходит только один участник и остается до конца.

Пример 3:

В клубе $$$4$$$ участника, и только одно мнение будет обсуждаться во время встречи. Проанализируем возможные исходы в зависимости от участников на встрече:

  • Если придет только первый участник, после встречи он останется один.
  • Если первый участник придет со вторым или третьим участником, в обсуждении будет ничья, и они оба уйдут.
  • Если первый участник придет со вторым и третьим участниками, первый участник окажется в меньшинстве и уйдет после обсуждения, что противоречит условию.
  • Если придут первый и четвертый участники, они согласятся во время обсуждения и оба останутся до конца.
  • Если придут первый, второй и четвертый участники, второй участник окажется в меньшинстве во время обсуждения, и после него останутся только первый и четвертый участники. То же самое произойдет, если второго участника заменить на третьего.
  • Если придут все четыре участника, во время обсуждения будет ничья, и все уйдут.

Максимальное количество участников, оставшихся после встречи, составляет $$$2$$$.

Пример 4:

В клубе $$$5$$$ участников, и во время встречи будут обсуждаться $$$4$$$ мнения.

Один из способов достичь максимального количества участников — если на встречу придут только первый, третий и пятый участники. В этом случае все они согласятся во время первых двух обсуждений, после чего третий участник окажется в меньшинстве во время третьего обсуждения. Затем первый и пятый участники согласятся в последнем обсуждении, и эти два участника останутся до конца встречи.

Пример 5:

В клубе $$$4$$$ участника, и будут обсуждаться $$$2$$$ мнения.

Если на встречу придут первые три участника, первый участник окажется в меньшинстве во время первого обсуждения и покинет клуб. После этого второй и третий участники будут не согласны со вторым мнением, и они оба останутся до конца встречи. Таким образом, после встречи останется 2 участника, но это недопустимый исход, так как это вынуждает первого участника уйти. Следовательно, максимальное количество в 1 участник достигается, если на встречу придет только первый участник.