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>).
n = int(input())
l = list(map(int,input().split()))
dp = []
for i in range(n):
    dp.append(1)
d = {}
for i in range(2,round(l[0]**0.5)+1):
    if l[0]%i==0:
        d.setdefault(i,0)
        while l[0]%i==0:
            l[0] = l[0]//i
if l[0]>=2:
    d.setdefault(2,0)
for i in range(1,n):
    temp = round(l[i]**0.5)+1
    #print(temp)
    for j in range(2,temp):
        #print("j = ",j)
        if l[i]%j==0:
            if j in d.keys():
                dp[i] = max(dp[i],dp[d[j]]+1)
                d[j] = i
            else:
                d.setdefault(j,i)
            while l[i]%j==0:
                l[i] = l[i]//j
    if l[i]>2:
        if l[i] in d.keys():
            dp[i] = max(dp[i],dp[d[l[i]]]+1)
            d[l[i]] = i
        else:
            d.setdefault(l[i],i)
print(max(dp))