Good Sequences

输入 $n$ 个数 $a_1, a_2, \dots, a_n$，保证严格递增。 如果一个序列 $x_1, x_2, \dots, x_k$ 能够满足条件，那就是一个好序列： - $\forall i \in [1, k)$，有 $x_i < x_{i+1}$； - $\forall i \in [1, k)$，有 $\gcd(x_i, x_{i+1}) > 1$； - $\forall i \in [1, k]$，有 $x_i \in a$。 问序列最长是多少。

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}&lt;x_{i+1} $ for each $ i $ $ (1<=i<=k-1) $ . - No two adjacent elements are coprime, i.e. $ gcd(x_{i},x_{i+1})&gt;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.

The input consists of two lines. The first line contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ) — 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}<=10^{5}; a_{i}&lt;a_{i+1} $ ).

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

5
2 3 4 6 9

4

9
1 2 3 5 6 7 8 9 10

4

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.