B. Мастер Mex-ов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$. Цена массива $$$a$$$ — это MEX$$$^{\dagger}$$$ массива $$$[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$$$. Найдите минимальную цену $$$a$$$, если в нём разрешается переставлять элементы массива $$$a$$$ местами. Обратите внимание, что вам не нужно искать массив $$$a$$$, на котором достигается минимальная цена.

$$$^{\dagger}$$$ MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Входные данные

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

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$2\le n\le 2\cdot10^5$$$).

Вторая строка каждого набора содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2\cdot 10^5$$$).

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

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

Для каждого набора входных данных выведите минимальную цену $$$a$$$ после перестановки элементов $$$a$$$ в любом порядке.

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

В первом наборе входных данных оптимальной является перестановка $$$a$$$, равная $$$[0,0]$$$, ценой этого массива является MEX массива $$$[0+0]=[0]$$$, равный $$$1$$$.

Во втором наборе оптимальной является перестановка $$$a$$$ равная $$$[0,1,0]$$$, ценой этого массива является MEX массива $$$[0+1,1+0]=[1,1]$$$, равного $$$0$$$.