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

У Tokitsukaze есть последовательность $$$a$$$ длины $$$n$$$. Для каждой операции она выбирает два числа $$$a_i$$$ и $$$a_j$$$ ($$$i \ne j$$$; $$$1 \leq i,j \leq n$$$).

  • Если $$$a_i = a_j$$$, измените одно из них на $$$0$$$.
  • В противном случае измените их оба на $$$\min(a_i, a_j)$$$.

Tokitsukaze хочет узнать, за какое минимальное количество операций можно изменить все числа в последовательности на $$$0$$$. Можно доказать, что ответ всегда существует.

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

Первая строка содержит единственное положительное целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Для каждого набора входных данных в первой строке записано одно целое число $$$n$$$ ($$$2 \leq n \leq 100$$$) — длина последовательности $$$a$$$.

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

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

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

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

В первом наборе входных данных один из возможных способов изменить все числа в последовательности на $$$0$$$:

В $$$1$$$-й операции $$$a_1 < a_2$$$, после операции $$$a_2 = a_1 = 1$$$. Теперь последовательность $$$a$$$ равна $$$[1,1,3]$$$.

В $$$2$$$-й операции $$$a_1 = a_2 = 1$$$, после операции $$$a_1 = 0$$$. Теперь последовательность $$$a$$$ равна $$$[0,1,3]$$$.

В $$$3$$$-й операции $$$a_1 < a_2$$$, после операции $$$a_2 = 0$$$. Теперь последовательность $$$a$$$ равна $$$[0,0,3]$$$.

В $$$4$$$-й операции $$$a_2 < a_3$$$, после операции $$$a_3 = 0$$$. Теперь последовательность $$$a$$$ равна $$$[0,0,0]$$$.

Таким образом, минимальное количество операций составляет $$$4$$$.