C. Никита и ТЧ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Никита — студент, увлеченный теорией чисел и алгоритмами. Он столкнулся с интересной задачей, связанной с массивом чисел.

Допустим, у Никиты есть массив целых чисел $$$a$$$ длины $$$n$$$. Назовём подпоследовательность$$$^\dagger$$$ массива особенной, если её наименьшее общее кратное (НОК) не содержится в $$$a$$$. НОК пустой подпоследовательности равен $$$0$$$.

Никита задался вопросом: какова длина самой длинной особенной подпоследовательности массива $$$a$$$? Помогите ему ответить на этот важный вопрос!

$$$^\dagger$$$ Последовательность $$$b$$$ является подпоследовательностью $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов, не изменяя порядок оставшихся элементов. Например, $$$[5,2,3]$$$ является подпоследовательностью $$$[1,5,7,8,2,4,3]$$$.

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

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

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

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

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

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

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

Пример
Входные данные
6
5
1 2 4 8 16
6
3 2 10 20 60 1
7
2 3 4 6 12 100003 1200036
9
2 42 7 3 6 7 7 1 6
8
4 99 57 179 10203 2 11 40812
1
1
Выходные данные
0
4
4
5
8
0
Примечание

В первом наборе входных данных НОК любой непустой подпоследовательности будет содержаться в $$$a$$$, поэтому ответ $$$0$$$.

Во втором наборе входных данных можно взять подпоследовательность $$$[3, 2, 10, 1]$$$, ее НОК — число $$$30$$$, которое не содержится в $$$a$$$.

В третьем наборе входных данных можно взять подпоследовательность $$$[2, 3, 6, 100\,003]$$$, ее НОК — число $$$600\,018$$$, которое не содержится в $$$a$$$.