B. НИТ уничтожает вселенную
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для набора целых чисел $$$S$$$ определим $$$\operatorname{mex}(S)$$$ как наименьшее неотрицательное целое число, которое не встречается в $$$S$$$.

Гражданин НИТ решил уничтожить вселенную. К сожалению, он не настолько могуществен, как Танос, так что для достижения своей цели ему придётся щёлкнуть пальцами несколько раз.

Вселенная может быть представлена массивом $$$a$$$ длины $$$n$$$ в 1-индексации. Когда НИТ щёлкает пальцами, он осуществляет следующую операцию над массивом:

  • Он выбирает целые числа $$$l$$$ и $$$r$$$, такие что $$$1\le l\le r\le n$$$. Пусть $$$w=\operatorname{mex}(\{a_l,a_{l+1},\dots,a_r\})$$$. Тогда для всех $$$l\le i\le r$$$ нужно заменить $$$a_i$$$ на $$$w$$$.

Будем говорить, что вселенная уничтожена, если и только если $$$a_i=0$$$ для всех $$$1\le i\le n$$$.

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

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

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

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

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

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

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

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

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

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

Во втором наборе входных данных одним из оптимальных решений будет выбор одной операции с $$$l=2$$$, $$$r=5$$$.

В третьем наборе входных данных одним из оптимальных решений будет выбор двух операций с параметрами $$$l=4$$$, $$$r=4$$$ и $$$l=2$$$, $$$r=6$$$ соответственно.

В четвёртом наборе входных данных одним из оптимальных решений будет выбор одной операции с $$$l=1$$$, $$$r=1$$$.