题目描述

参考图 5，标签树是一个二维非负整数数组（数组大小为 $2^k\times2^k$，其中 $k$ 为整数且 $2\leq k\leq20$）的层次化表示，通过逐步降低分辨率来构建一棵树。需要注意的是，对于一个 $n\times n$ 的数组，其索引范围是从 $0$ 到 $n - 1$。树中每个创建节点的值 $q(t, i, j)$ 是其四个子节点 $q(t + 1, 2i, 2j)$、$q(t + 1, 2i, 2j + 1)$、$q(t + 1, 2i + 1, 2j)$ 和 $q(t + 1, 2i + 1, 2j + 1)$ 的最小值，其中 $t$（$0\leq t\lt k$）是层级索引，$i$ 和 $j$ 是二维数组的索引。最底层的二维数组即为输入数组。

标签树将按照以下规则编码为一个二进制序列。标签树构建完成后，为每个节点关联一个升级值 $c(t, i, j)$，初始值设为 $0$。在节点编码过程中，升级值会被更新。编码从顶层节点（即层级索引为 $0$ 的节点）开始，并且在父节点编码完成之前，子节点不能进行编码。编码节点时，若其升级值 $c(t, i, j)$ 小于 $q(t, i, j)$，则输出一个 $0$ 比特，然后将 $c(t, i, j)$ 加 $1$；若 $q(t, i, j)$ 和 $c(t, i, j)$ 相等，则输出一个 $1$ 比特。节点编码完成后，所有升级值小于该节点升级值的后代节点的升级值将被更新为该编码节点的升级值。编码过程将持续进行，直到标签树中的所有节点都被编码。

例如，下面的编码从顶层节点开始，该节点的 $q(0, 0, 0) = 1$，$c(0, 0, 0) = 0$。由于 $c(0, 0, 0) \lt q(0, 0, 0)$，我们输出一个 $0$ 比特。接着，将 $c(0, 0, 0)$ 加 $1$，此时 $c(0, 0, 0) = q(0, 0, 0)$，所以输出一个 $1$ 比特。因此，顶层节点编码后的输出比特序列为 $01$。一旦 $q(0, 0, 0)$ 编码完成，所有升级值小于 $1$ 的后代节点的升级值将被更新为 $1$，如图 6(a) 所示。

在图 6(b) - (f) 中，我们用 “*” 标记已编码的节点。接下来，对 $q(1, 0, 0)$ 进行编码。此时 $c(1, 0, 0) = q(1, 0, 0) = 1$，输出一个 $1$ 比特，$q(1, 0, 0)$ 编码完成。根据更新规则，其后代节点的关联升级值再次更新（见图 6(b)）。继续对 $q(2, 0, 0)$ 进行编码，由于 $c(2, 0, 0) = q(2, 0, 0)$，该节点输出一个 $1$ 比特（见图 6(c)）。到目前为止，对 $q(0, 0, 0)$、$q(1, 0, 0)$ 和 $q(2, 0, 0)$ 编码后的输出为 $0111$。

接下来，对 $q(2, 1, 0)$（其值为 $3$）进行编码。此时无需再次对其祖先节点进行编码，因为其祖先节点 $q(1, 0, 0)$ 和 $q(0, 0, 0)$ 已经编码完成。因此，可以直接对 $q(2, 1, 0)$ 进行编码。由于 $c(2, 1, 0)$ 在等于 $q(2, 1, 0)$ 之前需要增加两次，所以其输出编码为 $001$（见图 6(d)）。

继续这个例子，假设要对 $q(2, 2, 0)$（其值为 $2$）进行编码。由于其父节点 $q(1, 1, 0)$ 尚未编码，所以需要先对其进行编码。其输出编码为 $01$，相关升级值更新如图 6(e) 所示。再对 $q(2, 2, 0)$ 进行编码时，仅输出一个 $1$ 比特（见图 6(f)）。

输入

第一行包含一个正整数 $N$（$N\leq10$），表示测试用例的数量。对于每个测试用例，第一行包含一个整数 $k$，表示数组大小为 $2^k\times2^k$。接下来的 $2^k$ 行表示一个 $2^k\times2^k$ 的数组，数组的行逐行列出，每行包含 $2^k$ 个非负整数，整数之间用空格分隔。

输出

对于每个测试用例，在一行中输出对输入数组进行编码所需的比特数。

输入样例

3
2
1 3 2 3
2 2 2 4
2 2 2 2
2 3 4 4
2
2 1 1 4
1 3 2 3
1 1 3 2
2 1 3 5
3
4 1 3 2 5 2 1 2
1 1 3 4 1 1 3 2
3 3 2 1 2 4 1 2
4 2 4 1 2 3 4 1
1 2 3 2 4 4 1 2
3 2 3 2 4 4 2 4
4 5 1 1 1 1 3 3
3 1 2 3 2 3 4 2

输出样例

37
38
155

题目来源

台湾 2002 年竞赛题目