C. Ментально монументально (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам требуется найти только значение $$$f(a)$$$.

Для любого массива $$$[c_1, c_2, \ldots, c_m]$$$ определим $$$f(c)$$$ как максимально возможное значение $$$\operatorname{mex}(c)$$$$$$^{\text{∗}}$$$, которое можно получить, выполнив следующую операцию ровно один раз:

  • Выбрать целочисленный массив $$$[b_1, b_2, \ldots, b_m]$$$ такой, что $$$b_i \ge 1$$$ для всех $$$1 \le i \le m$$$;
  • Присвоить $$$c_i := c_i \, \bmod \, b_i$$$$$$^{\text{†}}$$$ для каждого $$$1 \le i \le m$$$.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел. Определите значение $$$f(a)$$$.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(c)$$$ обозначает минимальное целое неотрицательное число, отсутствующее среди элементов массива $$$c$$$. Например, $$$\operatorname{mex}([2,2,1])=0$$$, потому что $$$0$$$ не принадлежит массиву, а $$$\operatorname{mex}([0,3,1,2])=4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ присутствуют в массиве, а $$$4$$$ — нет.

$$$^{\text{†}}$$$$$$u \bmod v$$$ обозначает остаток от деления $$$u$$$ на $$$v$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Гарантируется, что сумма $$$\max(a_1,a_2,\ldots,a_n)$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
4
4
0 1 2 3
2
6 7
6
8 1 7 6 4 3
9
9 9 8 2 4 4 3 5 3
Выходные данные
4
2
5
6
Примечание

Для первого набора входных данных выбор $$$b = [1, 2, 3, 4]$$$ оставляет массив $$$a$$$ без изменений, и мы получаем $$$\operatorname{mex}(a) = 4$$$.

Для второго набора входных данных выбор $$$b = [3, 3]$$$ делает $$$a = [0, 1]$$$. Следовательно, $$$\operatorname{mex}(a) = 2$$$.