CF2236A Games on the Train

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.

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 $ ).

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.