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

Дан массив $$$a$$$ из $$$n$$$ целых чисел. У этого массива изначально есть только одна копия, данная вам.

Можно делать два вида действий:

  1. Выбрать любой массив и создать его копию. После это появляется ещё один массив, равный выбранному.
  2. Поменять местами два элемента из любых копий (возможно, в одной копии) на любых позициях.

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

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

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

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

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

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

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

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

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

В первом наборе входных данных в массиве уже все числа равны, поэтому ответ равен $$$0$$$.

Во втором наборе входных данных сначала можно сделать копию данного массива. Тогда будут два одинаковых массива:

$$$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$$$ и $$$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$$$

После этого можно поменять местами элементы так, чтобы все нули оказались в одном массиве:

$$$[ \ 0 \ \underline{0} \ \underline{0} \ 3 \ 7 \ 0 \ ]$$$ и $$$[ \ \underline{1} \ 1 \ 3 \ 3 \ 7 \ \underline{3} \ ]$$$

Теперь создадим копию первого массива:

$$$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$$$, $$$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$$$ и $$$[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$$$

Поменяем местами элементы в первых двух копиях:

$$$[ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]$$$, $$$[ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]$$$ и $$$[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$$$.

В итоге за $$$6$$$ действий получили массив, в котором все элементы одинаковые.

Можно доказать, что невозможно получить ответ меньше.