A. MEX-уничтожение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дракон Эвирир пробрался в замок волшебника и нашел таинственное приспособление. Врожденные инстинкты дракона заставили его поиграть с приспособлением (уничтожить его)...

Дракон Эвирир нашел массив длины $$$n$$$ из целых неотрицательных чисел $$$a_1, a_2, \ldots, a_n$$$.

За одну операцию он может выбрать непустой подмассив$$$^{\text{∗}}$$$ $$$b$$$ массива $$$a$$$ и заменить его одним числом — значением $$$\operatorname{mex}(b)$$$$$$^{\text{†}}$$$. Он хочет использовать эту операцию некоторое количество раз, чтобы в результате массив $$$a$$$ состоял только из нулей. Можно доказать, что это всегда возможно при заданных ограничениях.

Каково минимальное количество операций, необходимое для достижения цели?

$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$d$$$, если $$$c$$$ может быть получен из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

$$$^{\text{†}}$$$Наименьшее исключенное (MEX) набора чисел $$$f_1, f_2, \ldots, f_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$f$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — длина $$$a$$$.

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

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

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

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

В первом наборе входных данных Эвирир может выбрать подмассив $$$b = [1, 2, 3]$$$ и заменить его на $$$\operatorname{mex}(1, 2, 3) = 0$$$, изменив $$$a$$$ с $$$[0, \underline{1, 2, 3}]$$$ на $$$[0, 0]$$$ (где выбранный подмассив подчеркнут). Следовательно, ответ равен $$$1$$$.

Во втором наборе входных данных $$$a$$$ уже состоит только из $$$0$$$, поэтому выполнение операций не требуется.

В третьем наборе входных данных Эвирир может изменять $$$a$$$ следующим образом: $$$[1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0]$$$, так как $$$\operatorname{mex}(0, 1, 0, 1) = 2$$$ и $$$\operatorname{mex}(1, 2) = 0$$$.

В четвертом наборе входных данных Эвирир может выбрать в качестве $$$b$$$ весь массив $$$a$$$, изменив значение $$$a$$$ с $$$[\underline{3, 1, 4, 1, 5}]$$$ на $$$[0]$$$.