在 Bajtowie 刚刚举办了一场盛大的 Bajt: Bitmingham 游戏锦标赛。每场 Bajt: Bitmingham 比赛恰好有三名玩家参加，他们必须在同一个地点会合才能进行比赛。

如你所知，Bajtowie 只有一条长路，路边有 $n$ 座建筑物，编号依次为 $1$ 到 $n$。

为了方便玩家，规定如果三名玩家分别住在编号为 $a, b, c$ 的建筑物中，则比赛将在中间的那座建筑物中进行，即编号为 $a, b, c$ 的中位数的建筑物。特别地，如果两名玩家住在同一座建筑物 $x$ 中，那么无论第三名玩家住在哪里，比赛都会在建筑物 $x$ 中进行。

你正在准备锦标赛的统计摘要。你知道每三名玩家之间最多进行过一次比赛。对于每座建筑物，你知道其中进行了多少场比赛：对于编号为 $i$ 的建筑物，进行了 $a_i$ 场比赛。但你忘记了锦标赛中共有多少名玩家……

请计算在不与已知信息矛盾的前提下，参加锦标赛的玩家的最少人数。

你需要解决 $t$ 个独立的测试用例。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 50$)，表示测试用例的数量。

每个测试用例由两行描述。第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示 Bajtowie 的建筑物数量。第二行包含一个整数序列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$)，表示在各建筑物中进行的比赛场数。你可以假设至少有一个 $a_i$ 为正数。

所有测试用例的 $n$ 之和不超过 $200\,000$。

输出格式

输出应包含 $t$ 行，第 $i$ 行应包含一个整数，表示可能参加锦标赛的最少人数。

样例

样例输入 1

4
1
1
1
57
5
0 3 4 3 0
2
4 4

样例输出 1

3
9
5
6

说明 1

在第一个测试用例中，进行一场比赛需要 3 名玩家。在第二个测试用例中，共有 57 场比赛；8 名玩家是不够的，因为那样最多只有 $\binom{8}{3} = 56$ 种不同的三人组合，因此需要第九名玩家。在第三个测试用例中，每座建筑物中可能住有一名玩家： 在第二座建筑物中，进行了来自建筑物 1, 2, 3；1, 2, 4 以及 1, 2, 5 的玩家之间的比赛； 在第三座建筑物中，进行了来自建筑物 1, 3, 4；1, 3, 5；2, 3, 4 以及 2, 3, 5 的玩家之间的比赛； * 在第四座建筑物中，进行了来自建筑物 1, 4, 5；2, 4, 5 以及 3, 4, 5 的玩家之间的比赛。

在第四个测试用例中，5 名玩家是不够的，因为在某座建筑物中最多只有两名玩家，这不足以凑出 4 组具有相应中位数的比赛。