Никита — студент, увлеченный теорией чисел и алгоритмами. Он столкнулся с интересной задачей, связанной с массивом чисел.
Допустим, у Никиты есть массив целых чисел \(a\) длины \(n\). Назовём подпоследовательность\(^\dagger\) массива особенной, если её наименьшее общее кратное (НОК) не содержится в \(a\). НОК пустой подпоследовательности равен \(0\).
Никита задался вопросом: какова длина самой длинной особенной подпоследовательности массива \(a\)? Помогите ему ответить на этот важный вопрос!
\(^\dagger\) Последовательность \(b\) является подпоследовательностью \(a\), если \(b\) может быть получена из \(a\) путем удаления нескольких (возможно, нуля или всех) элементов, не изменяя порядок оставшихся элементов. Например, \([5,2,3]\) является подпоследовательностью \([1,5,7,8,2,4,3]\).
Выходные данные
Для каждого набора выведите одно целое число — максимальную длину особенной подпоследовательности \(a\).
Примечание
В первом наборе входных данных НОК любой непустой подпоследовательности будет содержаться в \(a\), поэтому ответ \(0\).
Во втором наборе входных данных можно взять подпоследовательность \([3, 2, 10, 1]\), ее НОК — число \(30\), которое не содержится в \(a\).
В третьем наборе входных данных можно взять подпоследовательность \([2, 3, 6, 100\,003]\), ее НОК — число \(600\,018\), которое не содержится в \(a\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|