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

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Массив $$$x_1, x_2, \ldots, x_m$$$ называется красивым, если существует массив $$$y_1, y_2, \ldots, y_m$$$, такой что элементы $$$y$$$ различны (иными словами, $$$y_i\neq y_j$$$ для всех $$$1 \le i \lt j \le m$$$), и произведение $$$x_i$$$ и $$$y_i$$$ одинаково для всех $$$1 \le i \le m$$$ (иными словами, $$$x_i\cdot y_i = x_j\cdot y_j$$$ для всех $$$1 \le i \lt j \le m$$$).

Ваша задача — определить максимальный размер подпоследовательности$$$^{\text{∗}}$$$ массива $$$a$$$, которая является красивой.

$$$^{\text{∗}}$$$Последовательность $$$b$$$ является подпоследовательностью $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

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

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

Обратите внимание, что на сумму $$$n$$$ по всем наборам входных данных дополнительных ограничений нет.

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

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

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

В первом наборе входных данных весь массив $$$a = [1, 2, 3]$$$ уже является красивым. Возможный массив $$$y$$$ — это $$$[6, 3, 2]$$$. Он является допустимым, так как элементы $$$y$$$ различны, и $$$1\cdot 6 = 2\cdot 3 = 3\cdot 2$$$.

Во втором наборе входных данных подпоследовательность $$$[3, 1, 4, 5]$$$ является красивой. Возможный массив $$$y$$$ — это $$$[20, 60, 15, 12]$$$. Можно доказать, что весь массив $$$a = [3, 1, 4, 1, 5]$$$ не является красивым, поэтому максимальный размер подпоследовательности массива $$$a$$$, которая является красивой, равен $$$4$$$.