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 *
from sys import *
def is_prime(n):
    if n==1:
        return False
    elif n==2 or n==3:
        return True
    elif n%2==0:
        return False
    elif n%3==0:
        return False
    elif n<9:
        return True
    else:
        r=ceil(sqrt(n))
        f=5
        while f<=r:
            if n%f==0:
                return False
            if n%(f+2)==0:
                return False
            f+=6
        return True
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
d={}
ans=[1]*n
for i in range(n):
    tmp=0
    ele=-1
    if is_prime(a[i]):
        d[a[i]]=1
        continue
    for j in d:
        if gcd(j,a[i])>1:
            if 1+d[j]>tmp:
                tmp=1+d[j]
                ele=j
    if ele==-1:
        d[a[i]]=1
    else:
        d[a[i]]=tmp
        ans[i]=tmp
stdout.write(str(max(ans))+"\n")