B. Игра в пас
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даниэль наблюдает за игрой футбольной команды во время тренировки. Во время этой тренировки они хотят улучшить свои навыки паса.

В игре участвуют $$$n$$$ игроков, которые делают передачи друг другу. Тренировка закончилась, но к сожалению, поскольку мячи двигались слишком быстро, Даниэль не смог понять, сколько мячей находилось в игре. Единственное, что он знает, это количество пасов, сделанных каждым игроком за время тренировки.

Найдите минимально возможное количество мячей, которые участвовали в игре.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество игроков в команде.

Во второй строке набора задана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), где $$$a_i$$$ обозначает количество пасов, сделанных $$$i$$$-м игроком.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — ответ на задачу.

Пример
Входные данные
4
4
2 3 3 2
3
1 5 2
2
0 0
4
1000000000 1000000000 1000000000 1000000000
Выходные данные
1
2
0
1
Примечание

В первом наборе входных данных с единственным мячом игра могла проходить так:

$$$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$$$.

Во втором наборе входных данных выполнить передачи одним мячом невозможно. Один из возможных способов игры двумя мячами:

$$$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$.

$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$

В третьем наборе пасов не было, поэтому возможны $$$0$$$ мячей.