题目描述

达比尔、叶戈尔和阿尔谢尼刚上火车，决定玩一个游戏。达比尔有一个背包，里面装着无限个立方体。他用这些立方体搭了 $n$ 座塔，其中第 $i$ 座塔的高度为 $h_i$ 个立方体。

叶戈尔和阿尔谢尼必须为每座塔 $i$ 选择一个整数 $x_i$，并将其高度 恰好一次 增加 $x_i$。例如，若 $h$ = [$1, 3, 2, 2$]，$x$ = [$3, 2, 2, 8$]，则增加后 $h$ 变为 [$4, 5, 4, 10$]。他们的目标是使所有塔的高度相等。

为了让游戏更有趣，达比尔想选择一个整数 $k$ 并添加一个限制：每个 $x_i$ 必须满足 $1 \le x_i \le k$。请帮他找出能够完成游戏的最小 $k$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

随后是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5$）。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 6$）。

输出格式

对于每个测试用例，输出一个整数 — 使得所有塔的高度相等的最小 $k$ 值。

样例

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

3
5
6
1