题目描述

Roman 站在一个爆炸装置前。这个装置可以看作一个有 $N$ 层的金字塔，层数从 $1$ 到 $N$ 编号。第 $i$ 层有 $i$ 枚炸弹，记为 $B_{i,j}$，其中 $j$ 是该层中炸弹的编号。

对于每枚炸弹 $B_{i,j}$，已知它会在初始时刻之后 $T_{i,j}$ 秒爆炸。

Roman 需要按照下面的规则拆除所有炸弹：

1. 拆除一枚炸弹需要 $1$ 秒；
2. 若要拆除炸弹 $B_{i,j}$，必须先拆除它下面直接支撑它的两枚炸弹，即 $B_{i+1,j}$ 和 $B_{i+1,j+1}$。第 $N$ 层的炸弹下面没有其他炸弹，因此不受这条限制。

当所有炸弹都被拆除时，整个装置才算被成功拆除。

Roman 不想太匆忙，因此他想知道：最多可以延迟多少秒开始拆除，仍然能够成功拆除整个装置。设这个最大延迟为 $X$。等价地，你需要求最大的整数 $X$，使得把所有爆炸时间都改成

以后，仍然存在一种合法的拆除顺序，使得每枚炸弹都能在爆炸前拆除。

$X$ 也可能是负数。如果当前已经来晚了，无法完成拆除，但如果早来 $1$ 秒就可以完成，则 $X=-1$；如果必须早来 $2$ 秒才可以完成，则 $X=-2$，依此类推。

任务

给定 $Q$ 组测试数据。对于每组数据，给出 $N$ 以及所有 $T_{i,j}$，请输出对应的最大 $X$。

输入格式

第一行包含整数 $Q$，表示测试数据组数。

接下来依次给出 $Q$ 组测试数据。每组数据中：

第一行包含整数 $N$。

接下来 $N$ 行，第 $i$ 行包含 $i$ 个自然数，其中第 $j$ 个数为 $T_{i,j}$。

输出格式

输出 $Q$ 行。第 $t$ 行输出第 $t$ 组测试数据的答案 $X$。

数据范围

• $1 \le Q \le 5$
• $1 \le N \le 1000$
• $1 \le T_{i,j} \le 10^9$

子任务

样例

输入

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

输出

7
0
-2
0

样例解释

第一组数据中，$N=2$，共有 $N(N+1)/2=3$ 枚炸弹，且都在 $10$ 秒后爆炸。Roman 最多可以等 $7$ 秒再开始，之后分别在第 $8,9,10$ 秒拆除三枚炸弹。

第二组数据对应图示，必须立即开始拆除，答案为 $0$。

第三组数据中存在三枚一开始就会爆炸的炸弹，因此 Roman 需要早来 $2$ 秒才可能成功拆除，答案为 $-2$。