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 collections import defaultdict 
n = int(input()) 
l = list(map(int, input().split())) 
 
d = defaultdict(int) 

def fin_fac(x): 
    result = []
    i = 2
    while i*i <= x:
        # Check if i divides x without leaving a remainder
        if x % i == 0:
            result.append(i)
            # Handle the case explained in the 4th
            while x % i == 0: # In Python, // operator performs integer/floored division
                x = x// i 
        i += 1 
    if x >= 2: result.append(x)
    # Return the list of factors of x
    return result
ans = 1
for i in range (n) : 
    lp = fin_fac(l[i])
    cu = 1
    for f in lp : 
        d[f] += 1 
        cu = max(cu ,d[f]) 
    for f in lp : 
        d[f] = cu
    ans = max(ans , cu)
    # print(d, l[i])


print(ans)

     
        


