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.

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} < *a*_{i + 1}).

提交代码