CF1251B.Binary Palindromes

A palindrome is a string $t$ which reads the same backward as forward (formally, $t[i] = t[|t| + 1 - i]$ for all $i \in [1, |t|]$). Here $|t|$ denotes the length of a string $t$. For example, the strings 010, 1001 and 0 are palindromes.

You have $n$ binary strings $s_1, s_2, \dots, s_n$ (each $s_i$ consists of zeroes and/or ones). You can swap any pair of characters any number of times (possibly, zero). Characters can be either from the same string or from different strings — there are no restrictions.

Formally, in one move you:

• choose four integer numbers $x, a, y, b$ such that $1 \le x, y \le n$ and $1 \le a \le |s_x|$ and $1 \le b \le |s_y|$ (where $x$ and $y$ are string indices and $a$ and $b$ are positions in strings $s_x$ and $s_y$ respectively),
• swap (exchange) the characters $s_x[a]$ and $s_y[b]$.

What is the maximum number of strings you can make palindromic simultaneously?

回文串是指正读和反读都相同的字符串 $t$（形式化地，对所有 $i \in [1, |t|]$，均有 $t[i] = t[|t| + 1 - i]$）。其中 $|t|$ 表示字符串 $t$ 的长度。例如，字符串 010、1001 和 0 都是回文串。

你有 $n$ 个二进制字符串 $s_1, s_2, \dots, s_n$（每个 $s_i$ 仅由 0 和/或 1 组成）。你可以任意次（包括零次）交换任意两个字符。被交换的字符既可以来自同一字符串，也可以来自不同字符串——没有任何限制。

形式化地，在一次操作中，你需要：

• 选择四个整数 $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]$。

你最多能同时使多少个字符串成为回文串？

The first line contains single integer $Q$ ($1 \le Q \le 50$) — the number of test cases.

The first line on each test case contains single integer $n$ ($1 \le n \le 50$) — the number of binary strings you have.

Next $n$ lines contains binary strings $s_1, s_2, \dots, s_n$ — one per line. It's guaranteed that $1 \le |s_i| \le 50$ and all strings constist of zeroes and/or ones.

第一行包含一个整数 $Q$（$1 \le Q \le 50$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$），表示你拥有的二进制字符串的数量。

接下来的 $n$ 行每行包含一个二进制字符串 $s_1, s_2, \dots, s_n$。保证对每个 $i$，有 $1 \le |s_i| \le 50$，且所有字符串仅由字符 0 和/或 1 组成。

Print $Q$ integers — one per test case. The $i$-th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the $i$-th test case.

输出 $Q$ 个整数——每个测试用例输出一个整数。其中第 $i$ 个整数应为：在第 $i$ 个测试用例中，对给定字符串执行零次或多次交换操作后，所能同时得到的回文串的最大数量。

In the first test case, $s_1$ is palindrome, so the answer is $1$.

In the second test case you can't make all three strings palindromic at the same time, but you can make any pair of strings palindromic. For example, let's make $s_1 = \text{0110}$, $s_2 = \text{111111}$ and $s_3 = \text{010000}$.

In the third test case we can make both strings palindromic. For example, $s_1 = \text{11011}$ and $s_2 = \text{100001}$.

In the last test case $s_2$ is palindrome and you can make $s_1$ palindrome, for example, by swapping $s_1[2]$ and $s_1[3]$.

在第一个测试用例中，$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[2]$ 与 $s_1[3]$ 等方式使 $s_1$ 成为回文串。