Dabir、Egor 和 Arseniy 刚刚上了火车,决定玩游戏。达比尔有一个背包,里面有无数个立方体。他用它们建造了 $$$n$$$ 塔,其中 $$$i$$$ 塔的高度为 $$$h_i$$$ 立方体。
Egor 和 Arseniy 必须为每个塔 $$$i$$$ 选择一个整数 $$$x_i$$$ 并将其高度增加 $$$x_i$$$ 正好一次。例如,如果$$$h$$$ = [$$$1, 3, 2, 2$$$],$$$x$$$ = [$$$3, 2, 2, 8$$$],则增加$$$h$$$后将变为[$$$4, 5, 4, 10$$$]。他们的目标是使所有塔的高度相等。
为了让游戏更有趣,Dabir 想选择一个整数 $$$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$$$ 的最小值,这样可以使所有塔具有相同的高度。
示例
输入复制
421 332 6 455 4 6 6 143 3 3 3
输出复制
3561