异或网格问题

时间限制：5 秒
空间限制：256 MB

给定一个 $n \times m$ 的矩阵 $a$，每个格子包含一个非负整数。位于第 $i$ 行第 $j$ 列的整数记作 $a_{i,j}$。

定义 $f(i)$ 为第 $i$ 行所有整数的按位异或和，$g(j)$ 为第 $j$ 列所有整数的按位异或和。在一次操作中，你可以执行以下两种操作之一：

• 选择任意一行 $i$，然后令 $a_{i,j} := g(j)$ 对所有 $1 \le j \le m$ 成立；
• 选择任意一列 $j$，然后令 $a_{i,j} := f(i)$ 对所有 $1 \le i \le n$ 成立。
• 

你可以执行任意多次操作（包括零次）。然后，我们通过计算最终矩阵中所有相邻格子对的绝对差之和来定义矩阵的美观度。

形式化地，矩阵的美观度为

$$\text{beauty}(a) = \sum |a_{x,y} - a_{r,c}|$$

其中求和遍历所有相邻的格子对。两个格子若共享一条边，则视为相邻。

求在所有可通过操作得到的矩阵中，美观度的最小值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 250$）—— 测试数据组数。

每组测试数据的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 15$）—— 矩阵的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$（$0 \le a_{i,j} < 2^{20}$）—— 描述矩阵 $a$。

保证所有测试数据中 $(n^2 + m^2)$ 的总和不超过 $500$。

输出格式

对于每组测试数据，输出一个整数 $b$ —— 可达到的最小美观度。

样例输入

4
1 2
1 3
2 3
0 1 0
5 4 4
2 3
0 2 4
4 5 1
3 3
1 2 3
4 5 6
7 8 9

样例输出

1
3
13
24

样例解释

我们用 $r(i)$ 表示对第 $i$ 行进行第一种操作，$c(j)$ 表示对第 $j$ 列进行第二种操作。

• 第一个测试数据：可以执行一次操作 $c(1)$，将 $a_{1,1}$ 替换为 $1 \oplus 3 = 2$。操作后的矩阵为
  2 3

美观度 $= |2-3| = 1$。

• 第二个测试数据：可以执行一次操作 $r(1)$，计算各列的异或和：
  $g(1) = 0 \oplus 5 = 5$，$g(2) = 1 \oplus 4 = 5$，$g(3) = 0 \oplus 4 = 4$。
  将第一行全部替换为这些值，得到矩阵
  5 5 4 5 4 4

美观度 $= |5-5| + |5-4| + |5-4| + |5-5| + |4-4| + |5-4| + |4-4| + |4-4|$ （计算所有相邻对），结果为 $3$。

• 第三个测试数据：达到最小美观度的最佳操作序列为：$c(3)$，然后 $r(2)$，然后 $c(2)$。最终得到的矩阵为
  0 4 6 4 5 6

其美观度为 $13$。

• 第四个测试数据：输入的是一个 $3 \times 3$ 矩阵，通过一系列操作可以得到美观度 $24$。具体操作序列略。