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.

Input

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}$).

Output

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

Note

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.