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>).
# import math
# import collections
# from itertools import permutations
# from itertools import combinations
# import sys
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')


'''def is_prime(n):
    j=2
    while j*j<=n:
        if n%j==0:
            return 0
        j+=1
    return 1'''


'''def gcd(x, y):
    while(y):
        x, y = y, x % y
    return x'''

'''fact=[]
def factors(n) :
     
    i = 1
    while i <= math.sqrt(n):
         
        if (n % i == 0) :
             
            if (n / i == i) :
                fact.append(i)

            else :
    
                fact.append(i)
                fact.append(n//i)
        i = i + 1'''

n = 100001
p = [0] * n
y = [[] for i in range(n)]
y[1] = [1]
for i in range(2, n):
    if not y[i]:
        y[i] = [i]
        for j in range(2 * i, n, i): y[j].append(i)
 
def prob():
    
    n = int(input())
   
    # s=input()
    
    l = [int(x) for x in input().split()]

    # a,b = list(map(int , input().split()))

    for i in l:
        k = max(p[j] for j in y[i])+1

        for j in y[i]:
            p[j] = k

    print(max(p))


t=1
# t=int(input())

for _ in range(0,t):
    prob()