CF1251B Binary Palindromes

回文串是指一个字符串 $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$ 只包含数字 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]$ 这两个字符。 你能同时让最多多少个字符串变成回文串？

第一行包含一个整数 $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$，且所有字符串只包含数字 0 和/或 1。

输出 $Q$ 个整数，每个整数对应一个测试用例，表示通过若干次交换操作后，最多能同时有多少个字符串变成回文串。

在第一个测试用例中，$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$ 变成回文串。 由 ChatGPT 4.1 翻译