Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> are good.

Now she is interested in good sequences. A sequence *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*k*</sub> is called good if it satisfies the following three conditions:
 -  The sequence is strictly increasing, i.e. *x*<sub class="lower-index">*i*</sub> &lt; *x*<sub class="lower-index">*i* + 1</sub> for each *i* (1 ≤ *i* ≤ *k* - 1). -  No two adjacent elements are coprime, i.e. *gcd*(*x*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i* + 1</sub>) &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<sup class="upper-index">5</sup>) — the number of good integers. The second line contains a single-space separated list of good integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> in strictly increasing order (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>; *a*<sub class="lower-index">*i*</sub> &lt; *a*<sub class="lower-index">*i* + 1</sub>).
from math import sqrt
def seive(n):
    if n==1:
        return [0,1]
    a = [i for i in range(n+1)]
    for i in range(2,int(sqrt(n)+1)+1):
        if a[i]==i:
            for j in range(i*i, n+1, i):
                if a[j]==j:
                    a[j] = i
    return a

def cpf(n):
    ans = set()
    while spf[n]!=n:
        ans.add(spf[n])
        n//=spf[n]
    ans.add(spf[n])
    return ans
n = int(input())
a = [int(i) for i in input().strip().split()]
d = {}
dp = [0 for i in range(n)]
spf = seive(a[n-1])
ans = 1
for i in range(n):
    pf = cpf(a[i])
    for p in pf:
        dp[i] = max(dp[i],d.get(p,0)+1)
    for p in pf:
        d[p] = max(d.get(p,0),dp[i])
    ans = max(ans,dp[i])
print(ans)