A. Games on the Train
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Dabir, Egor, and Arseniy just got on the train and decided to play a game. Dabir has a backpack with an infinite number of cubes. He built $$$n$$$ towers from them, where the $$$i$$$-th tower has height $$$h_i$$$ cubes.

Egor and Arseniy must choose an integer $$$x_i$$$ for each tower $$$i$$$ and increase its height by $$$x_i$$$ exactly once. For example, if $$$h$$$ = [$$$1, 3, 2, 2$$$], $$$x$$$ = [$$$3, 2, 2, 8$$$], then after increasing $$$h$$$ it will become [$$$4, 5, 4, 10$$$]. Their goal is to make the heights of all towers equal.

To make the game more interesting, Dabir wants to choose an integer $$$k$$$ and add a restriction: each $$$x_i$$$ must satisfy $$$1 \le x_i \le k$$$. Help him find the smallest $$$k$$$ for which it is possible to finish the game.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5$$$).

The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 6$$$).

Output

For each test case, output a single integer — the minimum value of $$$k$$$ such that it is possible to make all towers have equal height.

Example
Input
4
2
1 3
3
2 6 4
5
5 4 6 6 1
4
3 3 3 3
Output
3
5
6
1