B. Двоичные палиндромы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Палиндром — это строка $$$t$$$, которая одинаково читается как слева направо, так и справа налево (формально, $$$t[i] = t[|t| + 1 - i]$$$ для всех $$$i \in [1, |t|]$$$). Здесь и далее $$$|t|$$$ обозначает длину строки $$$t$$$. Например, строки 010, 1001 и 0 — палиндромы.

У вас есть $$$n$$$ двоичных строк $$$s_1, s_2, \dots, s_n$$$ (каждая $$$s_i$$$ состоит только из нулей и/или единиц). Вы можете менять местами любую пару символов любое количество раз (возможно, ноль раз). Символы могут быть как из одной строки, так и из разных строк — ограничений нет.

Формально, одна операция обмена выглядит следующим образом:

  • вы выбираете четыре целых числа $$$x, a, y, b$$$, такие что $$$1 \le x, y \le n$$$, $$$1 \le a \le |s_x|$$$ и $$$1 \le b \le |s_y|$$$ (где $$$x$$$ и $$$y$$$ — номера строк, а $$$a$$$ и $$$b$$$ — позиции в соответствующих строках $$$s_x$$$ и $$$s_y$$$),
  • меняете местами символы $$$s_x[a]$$$ и $$$s_y[b]$$$.

Какое максимальное количество строк вы сможете сделать палиндромами одновременно?

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

В первой строке задано одно число $$$Q$$$ ($$$1 \le Q \le 50$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных задано единственное целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество двоичных строк у вас в наличии.

В следующих $$$n$$$ строках заданы двоичные строки $$$s_1, s_2, \dots, s_n$$$ — по одной в строке. Гарантируется, что $$$1 \le |s_i| \le 50$$$ и все строки состоят из нулей и/или единиц.

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

Выведите $$$Q$$$ чисел — по одному на набор входных данных. $$$i$$$-е число — это максимальное количество палиндромов, которые вы сможете получить одновременно, применяя операцию обмена символов ноль или более раз на строках из $$$i$$$-го набора.

Пример
Входные данные
4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111
Выходные данные
1
2
2
2
Примечание

В первом наборе $$$s_1$$$ — уже палиндром, поэтому ответ равен $$$1$$$.

Во втором наборе вы не можете сделать все три строки палиндромами одновременно, но вы сможете сделать палиндромами любую пару из них. Например, сделаем $$$s_1 = \text{0110}$$$, $$$s_2 = \text{111111}$$$ и $$$s_3 = \text{010000}$$$.

В третьем наборе вы можете сделать обе строки палиндромами. Например, $$$s_1 = \text{11011}$$$ и $$$s_2 = \text{100001}$$$.

В последнем наборе $$$s_2$$$ — палиндром и вы можете сделать $$$s_1$$$ палиндромом, например, поменяв местами $$$s_1[2]$$$ и $$$s_1[3]$$$.