В Байтове только что прошел великий турнир по игре «Байт: Битмингем». В одной игре «Байт: Битмингем» принимают участие ровно три игрока, которые должны встретиться в одном месте, чтобы провести партию.

Как вы, вероятно, знаете, в Байтове есть только одна длинная дорога, вдоль которой стоят $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$), обозначающее количество зданий в Байтове. Во второй строке находится последовательность целых чисел $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

Пример 2

3
9
5
6

Примечание

В первом тестовом случае для проведения одной игры требуется 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 тройки с соответствующей медианой.