Палиндром — это строка \(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\) чисел — по одному на набор входных данных. \(i\)-е число — это максимальное количество палиндромов, которые вы сможете получить одновременно, применяя операцию обмена символов ноль или более раз на строках из \(i\)-го набора.
Примечание
В первом наборе \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111
|
1
2
2
2
|