Вам задан массив \(a\) длины \(n\), состоящий из целых чисел. Вы можете применять следующую операцию, состоящую из нескольких шагов, над массивом \(a\) ноль или более раз:
Например, если \(n=6\) и \(a=[1, 6, 1, 1, 4, 4]\), то вы можете произвести следующую последовательность операций:
Каким может быть минимальный размер массива после применения к нему некоторой последовательности операций?
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следуют \(t\) наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — длина массива \(a\).
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — минимальный возможный размер массива после применения к нему некоторой последовательности операций.
5 6 1 6 1 1 4 4 2 1 2 2 1 1 5 4 5 4 5 4 6 2 3 2 1 3 1
0 0 2 1 0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач