G. 网格优化
每个测试点时间限制：$7$ 秒
内存限制：$1024$ MB

考虑一个 $n$ 行 $n$ 列的网格图。令第 $x$ 行第 $y$ 列的格子为 $(x, y)$。
对于所有满足 $1 \le x < n$，$1 \le y \le n$ 的位置，存在一条从 $(x, y)$ 指向 $(x+1, y)$ 的有向边，其权值为非负整数 $d_{x, y}$。
对于所有满足 $1 \le x \le n$，$1 \le y < n$ 的位置，存在一条从 $(x, y)$ 指向 $(x, y+1)$ 的有向边，其权值为非负整数 $r_{x, y}$。

初始时，你在 $(1, 1)$，有一个空集合 $S$。你需要沿着边走，最终到达 $(n, n)$。每当你经过一条边时，它的权值会被插入到 $S$ 中。
请最大化当你到达 $(n, n)$ 时，$S$ 的 $\operatorname{MEX}^*$。

$^*$ 数组的 $\operatorname{MEX}$（最小排除值）是不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 $\operatorname{MEX}$ 是 $0$，因为 $0$ 不属于该数组。
• $[3,1,0,1]$ 的 $\operatorname{MEX}$ 是 $2$，因为 $0$ 和 $1$ 属于该数组，但 $2$ 不属于。
• $[0,3,1,2]$ 的 $\operatorname{MEX}$ 是 $4$，因为 $0,1,2,3$ 属于该数组，但 $4$ 不属于。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 20$）——网格的行数和列数。

接下来的 $n-1$ 行，每行包含 $n$ 个整数，之间用空格分隔——矩阵 $d$（$0 \le d_{x, y} \le 2n-2$）。

接下来的 $n$ 行，每行包含 $n-1$ 个整数，之间用空格分隔——矩阵 $r$（$0 \le r_{x, y} \le 2n-2$）。

保证所有测试用例的 $n^3$ 之和不超过 $8000$。

输出格式

对于每个测试用例，输出一行一个整数——当你到达 $(n, n)$ 时 $S$ 的最大可能 $\operatorname{MEX}$。

示例

输入 $1$

2
3
1 0 2
0 1 3
2 1
0 3
3 0
3
1 2 0
0 1 2
2 0
1 2
0 1

输出 $1$

3
2

输入 $2$

1
10
16 7 3 15 9 17 1 15 9 0
4 3 1 12 13 10 10 14 6 12
3 1 3 9 5 16 0 12 7 12
11 4 8 7 13 7 15 13 9 2
2 3 9 9 4 12 17 7 10 15
10 6 15 17 13 6 15 9 4 9
13 3 3 14 1 2 10 10 12 16
8 2 9 13 18 7 1 6 2 6
15 12 2 6 0 0 13 3 7 17
7 3 17 17 10 15 12 14 15
4 3 3 17 3 13 11 16 6
16 17 7 7 12 5 2 4 10
18 9 9 3 5 9 1 16 7
1 0 4 2 10 10 12 2 1
4 14 15 16 15 5 8 4 18
7 18 10 11 2 0 14 8 18
2 17 6 0 9 6 13 5 11
5 15 7 11 6 3 17 14 5
1 3 16 16 13 1 0 13 11

输出 $2$

14

说明

在第一个测试用例中，网格图及其中一条最优路径如下：

在第二个测试用例中，网格图及其中一条最优路径如下：