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 sys
import math
input = sys.stdin.readline
def my_key (a,  b ):
    res = str(a)+" " + str(b)
    return res

n = int (input()) 
arr = list (map(int, input().split(' '))) 
dp = dict()
def solve(ind, ls , res):
    if (ind == n ):
        return res 
    akey = my_key(ind,ls)
    if akey in dp.keys(): 
        return dp[akey]
    
    if (math.gcd(ls,arr[ind]) > 1 ):
        dp[akey] = max(solve(ind+1,arr[ind],res+1), solve(ind+1, ls , res ))
        return dp[akey]
    dp[akey] = solve(ind+1, ls , res ) 
    return dp[akey]    
res = 0
for i in range (n):
    res = max(res,solve(i+1, arr[i],1 ))
print(res)