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

У Геумджэ есть массив $$$a$$$, состоящий из $$$n$$$ нулей. Его цель — преобразовать его в заданный целевой массив, используя минимальное количество операций.

Он может выполнять следующие два типа операций любое количество раз, в любом порядке:

  1. Увеличить: Выбрать любое целое положительное число $$$x$$$ и увеличить все элементы массива $$$a$$$ на $$$x$$$. Другими словами, он выбирает целое положительное число $$$x$$$, и для каждого $$$i$$$ ($$$1 \le i \le n$$$) заменяет $$$a_i$$$ на $$$a_i + x$$$.
  2. Разбить: Сделать некоторые элементы (возможно, ни один или все) массива $$$a$$$ равными $$$0$$$. Другими словами, для каждого $$$i$$$ ($$$1 \le i \le n$$$) он либо заменяет $$$a_i$$$ на $$$0$$$, либо оставляет его прежним.

Учитывая конечное целевое состояние массива $$$a$$$, найдите минимальное общее количество операций (как Увеличить, так и Разбить), которые необходимо выполнить Геумджэ.

Можно показать, что для любого конечного массива всегда существует искомая последовательность операций.

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

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество элементов в массиве $$$a$$$.

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

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

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

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

Объяснение первого набора входных данных:

Целевой массив равен $$$[1, 1, 3]$$$. Возможная последовательность из 3 операций (что является минимумом) такова:

  1. Изначально массив равен $$$[0, 0, 0]$$$. После операции Увеличить с $$$x = 2$$$ массив становится $$$[2, 2, 2]$$$.
  2. Затем, после операции Разбить над первыми двумя элементами, массив становится $$$[0, 0, 2]$$$.
  3. Наконец, после операции Увеличить с $$$x = 1$$$ массив становится $$$[1, 1, 3]$$$.

Мы использовали $$$2$$$ операции Увеличить и $$$1$$$ операцию Разбить — суммарно $$$3$$$ операции.

Объяснение второго набора входных данных:

Целевой массив равен $$$[100]$$$. Одна операция Увеличить с $$$x = 100$$$ дает целевой массив.