Белка Лисска интересуется последовательностями. Также у нее есть предпочтения в целых числах. Она думает, что n целых чисел a1, a2, ..., an хорошие.
Теперь ей интересны хорошие последовательности. Последовательность x1, x2, ..., xk называется хорошей, если она удовлетворяет следующим трем условиям:
- Последовательность строго возрастает, то есть xi < xi + 1 для всех i (1 ≤ i ≤ k - 1).
- Никакие два соседних элемента не являются взаимно простыми, то есть gcd(xi, xi + 1) > 1 для всех i (1 ≤ i ≤ k - 1) (где gcd(p, q) обозначает наибольший общий делитель чисел p и q).
- Все элементы данной последовательности являются хорошими целыми числами.
Найдите длину самой длинной хорошей последовательности.
Выходные данные
Выведите единственное целое число — длину самой длинной хорошей последовательности.
Примечание
В первом примере следующие последовательности являются примерами хороших последовательностей: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. Длина самой длинной хорошей последовательности — 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3 4 6 9
|
4
|
|
2
|
9
1 2 3 5 6 7 8 9 10
|
4
|