← 返回题目列表

Codeforces · 2082/A

A. 二进制矩阵

中文机器翻译题面 查看原题

如果一个矩阵的所有元素都是 $$$0$$$ 或 $$$1$$$,则该矩阵称为二元矩阵。

Ecrade 调用二进制矩阵 $$$A$$$ 好 如果以下两个属性成立:

  • 矩阵$$$A$$$每行中所有数字的按位异或等于$$$0$$$。
  • 矩阵$$$A$$$每列中所有数字的按位异或等于$$$0$$$。

Ecrade 有一个大小为 $$$n \cdot m$$$ 的二进制矩阵。他感兴趣的是矩阵需要改变的最小数量 好.

不过,好像有点困难,所以请帮助他!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 400$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$1 \le n, m \le 100$$$)。

接下来是 $$$n$$$ 行,每行恰好包含 $$$m$$$ 个字符,仅由 $$$0$$$ 和 $$$1$$$ 组成,描述 Ecrade 矩阵的元素。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$5 \cdot 10^4$$$。

输出

对于每个测试用例,输出一个整数,即需要更改的元素的最小数量。

示例

输入
复制

7
3 3
010
101
010
3 3
000
000
000
3 3
100
010
001
3 3
101
010
000
3 3
000
010
000
1 4
0101
4 1
0
1
0
1

输出
复制

2
0
3
3
1
2
2

注意

在第一个测试用例中,他需要更改2个元素以获得以下矩阵$$$\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}$$$。

在第二个测试用例中,他可以不做任何改变,得到如下矩阵$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}$$$。

在第三个测试用例中,他需要更改3个元素以获得以下矩阵$$$\begin{pmatrix}1&0&1\\0&0&0\\1&0&1\end{pmatrix}$$$。