You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

称一个矩阵为二进制矩阵，当且仅当该矩阵中所有元素为 $0$ 或 $1$。

令 $S$ 为所有同时满足如下两个条件的 $n\times m$ 的二进制矩阵 $B=\{b_{i,j}\}$ 构成的集合：

• $B$ 每行中所有数的异或和为 $0$，即 $\forall ~1\le i\le n,~\mathop{\oplus}\limits_{j=1}^m b_{i,j}=0$；
• $B$ 每列中所有数的异或和为 $0$，即 $\forall ~1\le i\le m,~\mathop{\oplus}\limits_{i=1}^n b_{i,j}=0$。

Ecrade_ 有一个 $n\times m$ 的二进制矩阵 $A=\{a_{i,j}\}$，他定义一个 $n\times m$ 的二进制矩阵 $B=\{b_{i,j}\}$ 的权值为 $a_{i,j}$ 与 $b_{i,j}$ 中不同数的个数，即 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m[a_{i,j}\ne b_{i,j}]$。

Ecrade_ 想知道，$S$ 中矩阵权值的最小值为多少？

输入格式

从标准输入读入数据。

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行两个整数 $n,m$。
• 后 $n$ 行每行一个长为 $m$ 的数字串，其中第 $i+1$ 行第 $j$ 个字符表示 $a_{i,j}$。

输出格式

输出到标准输出。

对于每组测试数据，输出一行一个整数 $x$，表示 $S$ 中矩阵权值的最小值。

2
3 3
010
101
010
3 3
000
000
000

2
0

样例 1 解释

• 对于第一组测试数据，$S$ 中权值最小的一个矩阵为 $\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}$；
• 对于第二组测试数据，$S$ 中权值最小的一个矩阵为 $\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}$。

数据规模与约定

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（10 分）：$n=1$。
• 子任务 2（10 分）：$n,m\le 2$。
• 子任务 3（20 分）：$T\le 10,~n,m\le 4$。
• 子任务 4（20 分）：$n=2$。
• 子任务 5（40 分）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 2\times 10^5,~1\le n,m\le 10^3,~1\le \sum n\times m\le 10^6,~a_{i,j}\in\{0,1\}$。