说明

时间限制：1 Sec 内存限制：256 MB 输入文件：sushi.in 输出文件：sushi.out

在“二进制回转寿司店”里，每种寿司都用一串 $0$ 和 $1$ 来编号（比如 101 表示三文鱼卷，010 表示金枪鱼握）。店长小明今天准备了 $n$ 盘寿司，每盘上有一串编号。

寿司师傅有一个神奇的“叉子交换术”：他可以用叉子夹起编号中的任何两个字符（$0$ 或 $1$），把它们互换位置。这两个字符可以在同一盘寿司上，也可以在不同盘之间，想换多少次就换多少次，也可以不换。

小明的目标是：让尽可能多的寿司盘上的编号变成回文串（即正着读和倒着读一样，例如 010、1001 就是回文串，1010 不是回文串）。

交换规则（师傅的操作手册）：

一次交换操作中，选择四个整数 $x$, $a$, $y$, $b$，其中：

• $1 \le x, y \le n$，$x$ 为第一盘寿司的序号，$s_x$ 表示第一盘寿司的编号，$y$ 为第二盘寿司的序号，$s_y$ 表示第二盘寿司的编号，令 $|s_x|$ 表示字符串 $s_x$ 的长度

• $1 \le a \le |s_x|$（表示第一盘编号中的第 $a$ 个字符）

• $1 \le b \le |s_y|$（表示第二盘编号中的第 $b$ 个字符）

然后，交换这两盘寿司上指定位置的字符。

请你计算，最多可以得到多少个回文串。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 组询问，每组询问包含：

第一行为一个整数 $n$，表示有 $n$ 盘寿司；

接下来有 $n$ 行，每行一个二进制字符串 $s_1$、$s_2$、……、$s_n$，

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个整数，表示最多可以得到多少个回文串。

样例

样例 1

4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111

1
2
2
2

样例说明：

第 $1$ 组询问：只有一盘 0，它本身就是回文，答案为 $1$。

第 $2$ 组询问：三盘无法全部变回文，但可以让任意两盘变回文。比如通过交换，把三盘变成 0110、111111 和 010000。

第 $3$ 组询问：两盘都能变回文，比如变成 11011 和 100001。

第 $4$ 组询问：第二盘 11100111 本来就是回文，再交换第一盘的第 $2$ 和第 $3$ 个字符，让 001 变成 010，答案为 $2$。

数据范围

对 $20\%$ 的数据，$t=1$，$n=4$，且保证每一组询问中所有字符串的长度之和不超过 $100$

对另外 $30\%$ 的数据，$t=1$，$n=10$，且保证每一组询问中所有字符串的长度之和不超过 $3000$

对于 $100\%$ 的数据，$1 \le t \le 10$，$1 \le n \le 100$，且保证每一组询问中所有字符串的长度之和不超过 $2 \times 10^5$