给定一个大小为 $$$n \times m$$$ 的矩阵 $$$a$$$,其中每个单元格包含一个非负整数。矩阵第 $$$i$$$ 行和第 $$$j$$$ 列的交集处的整数称为 $$$a_{i,j}$$$。
让我们分别将 $$$f(i)$$$ 和 $$$g(j)$$$ 定义为第 $$$i$$$ 行和第 $$$j$$$ 列中所有整数的异或。在一次操作中,您可以:
- 选择任意行 $$$i$$$,然后为每个 $$$1 \le j \le m$$$ 分配 $$$a_{i,j} := g(j)$$$;或
- 选择任意列 $$$j$$$,然后为每个 $$$1 \le i \le n$$$ 分配 $$$a_{i,j} := f(i)$$$。
对矩阵的 $$$2$$$ 列应用运算的示例。
在此示例中,当我们对 $$$2$$$ 列应用操作时,该列中的所有元素都会更改:
- $$$a_{1,2} := f(1) = a_{1,1} \oplus a_{1,2} \oplus a_{1,3} \oplus a_{1,4} = 1 \oplus 1 \oplus 1 \oplus 1 = 0$$$
- $$$a_{2,2} := f(2) = a_{2,1} \oplus a_{2,2} \oplus a_{2,3} \oplus a_{2,4} = 2 \oplus 3 \oplus 5 \oplus 7 = 3$$$
- $$$a_{3,2} := f(3) = a_{3,1} \oplus a_{3,2} \oplus a_{3,3} \oplus a_{3,4} = 2 \oplus 0 \oplus 3 \oplus 0 = 1$$$
- $$$a_{4,2} := f(4) = a_{4,1} \oplus a_{4,2} \oplus a_{4,3} \oplus a_{4,4} = 10 \oplus 11 \oplus 12 \oplus 16 = 29$$$
您可以多次应用这些操作。然后,我们通过求和所有相邻单元对之间的绝对差来计算最终矩阵的 $$$\textit{beauty}$$$。
更正式地说,$$$\textit{beauty}(a) = \sum|a_{x,y} - a_{r,c}|$$$ 对于所有单元格 $$$(x, y)$$$ 和 $$$(r, c)$$$(如果它们相邻)。如果两个单元共用一条边,则认为它们是相邻的。
在所有可获得的矩阵中找到最小 $$$\textit{beauty}$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 250$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 15$$$) - 分别是 $$$a$$$ 的行数和列数。
接下来的 $$$n$$$ 行,每行包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$0 \le a_{i,j} < 2^{20}$$$) - 矩阵 $$$a$$$ 的描述。
保证所有测试用例的 $$$(n^2 + m^2)$$$ 总和不超过 $$$500$$$。
输出
对于每个测试用例,打印一个整数 $$$b$$$ — 矩阵的最小可能 $$$\textit{beauty}$$$。
示例
输入 #1
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
1 3 13 24
注意
我们将 $$$r(i)$$$ 表示为应用于第 $$$i$$$ 行的第一个类型操作,将 $$$c(j)$$$ 表示为应用于第 $$$j$$$ 列的第二个类型操作。
在第一个测试用例中,您可以应用操作 $$$c(1)$$$,该操作分配 $$$a_{1,1} := 1 \oplus 3 = 2$$$。然后,我们将收到这个矩阵:
23
在第二个测试用例中,您可以应用操作 $$$r(1)$$$,它分配:
- $$$a_{1,1} := g(1) = 0 \oplus 5 = 5$$$
- $$$a_{1,2} := g(2) = 1 \oplus 4 = 5$$$
- $$$a_{1,3} := g(3) = 0 \oplus 4 = 4$$$
执行运算后得到的矩阵为:
554544
在第三个测试用例中,实现最小 $$$\textit{beauty}$$$ 的最佳方法是应用三个操作:$$$c(3)$$$、$$$r(2)$$$ 和 $$$c(2)$$$。得到的矩阵是:
046456