{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"## 题目描述\n\n回文串是一个字符串 $t$,满足正反读都相同(形式上,对于所有 $i \\in [1, |t|]$,都满足 $t[i] \u003d t[|t| + 1 - i]$)。例如,字符串 `010`、`1001` 和 `0` 都是回文串。\n\n你有 $n$ 个二进制字符串 $s_1, s_2, \\dots, s_n$(每个 $s_i$ 由 `0` 和 `1` 组成)。你可以任意交换一对字符的位置(可以没有交换)。字符可以来自同一个字符串,也可以来自不同的字符串。\n\n形式上,一次操作包括:\n\n- 选择四个整数 $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$ 中的位置),\n- 交换(互换)字符 $s_x[a]$ 和 $s_y[b]$。\n\n最多能使多少个字符串同时成为回文串?\n\n## 输入格式\n\n第一行包含一个整数 $Q$($1 \\le Q \\le 50$)—— 输入中的测试用例数量。\n\n每个测试用例的第一行包含一个整数 $n$($1 \\le n \\le 50$)—— 二进制字符串的数量。\n\n接下来的 $n$ 行中,每行包含一个二进制字符串 $s_1, s_2, \\dots, s_n$。保证 $1 \\le |s_i| \\le 50$,且所有字符串由 `0` 和 `1` 构成。\n\n输入中可能有全为 `0` 和全为 `1` 的字符串出现。\n\n## 输出格式\n\n打印 $Q$ 个整数,每个测试用例一个整数。第 $i$ 个整数应该是在第 $i$ 个测试用例中,通过对字符串进行零次或多次交换后,能够同时得到的最大回文串数量。\n\n## 样例输入 1\n\n```\n4\n1\n0\n3\n1110\n100110\n010101\n2\n11111\n000001\n2\n001\n11100111\n```\n\n## 样例输出 1\n\n```\n1\n2\n2\n2\n```\n\n## 提示\n\n在第一个测试用例中,$s_1$ 是回文串,所以答案是 $1$。\n\n在第二个测试用例中,你无法同时使三个字符串都成为回文串,但你可以使任意一对字符串成为回文串。例如,设 $s_1 \u003d \\text{0110}$,$s_2 \u003d \\text{111111}$ 和 $s_3 \u003d \\text{010000}$。\n\n在第三个测试用例中,我们可以使两个字符串成为回文串。例如,$s_1 \u003d \\text{11011}$ 和 $s_2 \u003d \\text{100001}$。\n\n在最后一个测试用例中,$s_2$ 是回文串,你可以通过交换 $s_1[2]$ 和 $s_1[3]$ 来使 $s_1$ 成为回文串。\n\n\n\u003cp\u003eA palindrome is a string $$$t$$$ which reads the same backward as forward (formally, $$$t[i] \u003d t[|t| + 1 - i]$$$ for all $$$i \\in [1, |t|]$$$). Here $$$|t|$$$ denotes the length of a string $$$t$$$. For example, the strings \u003cspan class\u003d\"tex-font-style-tt\"\u003e010\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e1001\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e are palindromes.\u003c/p\u003e\n\u003cp\u003eYou 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.\u003c/p\u003e\n\u003cp\u003eFormally, in one move you:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003echoose 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),\u003c/li\u003e\n \u003cli\u003eswap (exchange) the characters $$$s_x[a]$$$ and $$$s_y[b]$$$.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eWhat is the maximum number of strings you can make palindromic simultaneously?\u003c/p\u003e"}},{"title":"Input","value":{"format":"MD","content":"\u003cp\u003eThe first line contains single integer $$$Q$$$ ($$$1 \\le Q \\le 50$$$) — the number of test cases.\u003c/p\u003e\n\u003cp\u003eThe first line on each test case contains single integer $$$n$$$ ($$$1 \\le n \\le 50$$$) — the number of binary strings you have.\u003c/p\u003e\n\u003cp\u003eNext $$$n$$$ lines contains binary strings $$$s_1, s_2, \\dots, s_n$$$ — one per line. It\u0027s guaranteed that $$$1 \\le |s_i| \\le 50$$$ and all strings constist of zeroes and/or ones.\u003c/p\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cp\u003ePrint $$$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.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1\n0\n3\n1110\n100110\n010101\n2\n11111\n000001\n2\n001\n11100111\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n2\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"\u003cp\u003eIn the first test case, $$$s_1$$$ is palindrome, so the answer is $$$1$$$.\u003c/p\u003e\n\u003cp\u003eIn the second test case you can\u0027t make all three strings palindromic at the same time, but you can make any pair of strings palindromic. For example, let\u0027s make $$$s_1 \u003d \\text{0110}$$$, $$$s_2 \u003d \\text{111111}$$$ and $$$s_3 \u003d \\text{010000}$$$.\u003c/p\u003e\n\u003cp\u003eIn the third test case we can make both strings palindromic. For example, $$$s_1 \u003d \\text{11011}$$$ and $$$s_2 \u003d \\text{100001}$$$.\u003c/p\u003e\n\u003cp\u003eIn 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]$$$.\u003c/p\u003e"}}]}