A94874.Good Sequences

松鼠 Liss 对数列很感兴趣。她也有自己喜欢的整数。她认为 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ 是好的整数。

现在她感兴趣于好的数列。一个数列 $x_{1},x_{2},...,x_{k}$ 被称作“好”的当且仅当它满足以下三个条件：

• 这个数列是严格递增的，即对每个 $i$ 满足 $1 \leq i \leq k-1$，都有 $x_{i} < x_{i+1}$。
• 任意相邻的两个元素都不是互质的，即对每个 $i$ 满足 $1 \leq i \leq k-1$，都有 $gcd(x_{i},x_{i+1}) > 1$（其中 $gcd(p, q)$ 表示整数 $p$ 和 $q$ 的最大公约数）。
• 数列中的所有元素都是好的整数。

请你求出最长好的数列的长度。

第一行包含一个整数 $n$，表示原序列中整数的个数。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$，表示给定的严格递增序列。

输出一个整数，表示最长好的数列的长度。

【样例解释 1】
原序列为 $\{2, 3, 4, 6, 9\}$。
我们可以构造出如下长度为 4 的和谐序列：
$\{2, 4, 6, 9\}$
验证相邻元素：

• $\gcd(2, 4) = 2 > 1$
• $\gcd(4, 6) = 2 > 1$
• $\gcd(6, 9) = 3 > 1$
  满足条件。其他可能的序列如 $\{2, 4, 6\}$ 或 $\{3, 6, 9\}$ 长度均为 3，不如 4 优。

【数据范围】
对于 $100\%$ 的数据，满足：

• $1 \le n \le 10^5$
• $1 \le a_i \le 10^5$
• 保证输入序列 $a$ 是严格递增的。