CF264B.Good Sequences

Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers _a_1, _a_2, ..., a__n are good.

Now she is interested in good sequences. A sequence _x_1, _x_2, ..., x__k is called good if it satisfies the following three conditions:

• The sequence is strictly increasing, i.e. x__i < x__i + 1 for each i (1 ≤ i ≤ k - 1).
• No two adjacent elements are coprime, i.e. gcd(x__i, x__i + 1) > 1 for each i (1 ≤ i ≤ k - 1) (where gcd(p, q) denotes the greatest common divisor of the integers p and q).
• All elements of the sequence are good integers.

Find the length of the longest good sequence.

松鼠 Liss 对序列很感兴趣。她对整数也有自己的偏好，认为 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$ 是“好的”。

现在她对“好序列”产生了兴趣。一个序列 $x_1,\,x_2,\,\dots,\,x_k$ 被称为好序列，当且仅当它满足以下三个条件：

• 该序列严格递增，即对每个 $i$（$1\le i\le k-1$），有 $x_i < x_{i+1}$；
• 任意两个相邻元素不互质，即对每个 $i$（$1\le i\le k-1$），有 $\gcd(x_i,\,x_{i+1}) > 1$（其中 $\gcd(p,\,q)$ 表示整数 $p$ 与 $q$ 的最大公约数）；
• 序列中的所有元素均为“好整数”。

请找出最长的“好序列”的长度。

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 105) — the number of good integers. The second line contains a single-space separated list of good integers _a_1, _a_2, ..., a__n in strictly increasing order (1 ≤ a__i ≤ 105; a__i < a__i + 1).

输入包含两行。第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示“好数”的个数。第二行包含用单个空格分隔的“好数”列表 $a_1,\,a_2,\,\dots,\,a_n$，该列表严格递增（$1 \leq a_i \leq 10^5$；$a_i < a_{i+1}$）。

Print a single integer — the length of the longest good sequence.

输出一个整数——最长“好”序列的长度。

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

在第一个例子中，以下序列是“好序列”的示例：[2; 4; 6; 9]、[2; 4; 6]、[3; 9]、[6]。最长“好序列”的长度为 4。