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 gcd
from math import ceil,sqrt
from collections import defaultdict

# The largest prime of that divides i where 2 <= i <= N
def largestPrime(N): # N log log N
    #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
    #[0, 1, 2, 3, 2, 5, 3, 7, 2, 3, 5,  11, 3,  13,  7,  5, 2,  17, 3,  19,  5, 7,  11, 23,  3,  5, 13,  3,  7, 29, 5]
    largerPrime = list(range(N+1))
    for i in range(2,N+1):
        if(largerPrime[i] == i):
            for j in range(i*2,N+1,i):
                largerPrime[j] = i
    return largerPrime
PrimeFactors = defaultdict(list)
def primeFactors(N): # N Log log N
    Large = largestPrime(N) # Requires largestPrime function
    for i in range(2,N+1):
        temp = i
        while(i!=1):
            fact = Large[int(i)]
            PrimeFactors[temp].append(Large[int(i)])
            while(i % fact == 0):
                i/=fact


N = int(input())
List = [int(x) for x in input().split()]
primeFactors(max(List) + 1)
d = defaultdict(int) # index is 1 based
for i in PrimeFactors[List[0]]:
    d[i] = 1
dp = [1] * (N+1)

for i in range(1,N):
    for j in PrimeFactors[List[i]]:
        if(d[j]!=0):
            dp[i] = max(dp[i], dp[d[j]-1]+1)
        d[j] = i+1
print(max(dp))