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

У Ехаба есть массив $$$a$$$ длины $$$n$$$. У него достаточно свободного времени, чтобы создать новый массив, состоящий из $$$n$$$ копий старого массива, записанных последовательно. Чему равна длина самой длинной возрастающей подпоследовательности нового массива?

Последовательность $$$a$$$ является подпоследовательностью массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$, удалив несколько (возможно, ноль или все) элементов. Самая длинная возрастающая подпоследовательность массива это самая длинная подпоследовательность, все элементы которой упорядочены в строго возрастающем порядке.

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

Первая строка содержит целое число $$$t$$$   — количество наборов входных данных. Далее следуют описания наборов входных данных.

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

Вторая строка содержит $$$n$$$ целых чисел, разделенных пробелом $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^9$$$)   — элементы массив $$$a$$$.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных, выведите длину самой длинной возрастающей подпоследовательности $$$a$$$, если вы объедините ее с собой $$$n$$$ раз.

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

В первом наборе входных данных примера, новый массив равен $$$[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$$$. Самая длинная возрастающая подпоследовательность в нем выделена жирным.

Во втором наборе входных данных примера, самая длинная возрастающая подпоследовательность равна $$$[1,3,4,5,9]$$$.