B. Хорошие последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Белка Лисска интересуется последовательностями. Также у нее есть предпочтения в целых числах. Она думает, что 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).
  • Все элементы данной последовательности являются хорошими целыми числами.

Найдите длину самой длинной хорошей последовательности.

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

Входные данные состоят из двух строк. Первая строка содержит единственное целое число n (1 ≤ n ≤ 105) — количество хороших целых чисел. Во второй строке задан список хороших целых чисел a1, a2, ..., an через пробел, в порядке строгого возрастания (1 ≤ ai ≤ 105; ai < ai + 1).

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

Выведите единственное целое число — длину самой длинной хорошей последовательности.

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

В первом примере следующие последовательности являются примерами хороших последовательностей: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. Длина самой длинной хорошей последовательности — 4.