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>).

max_len = 100000  # (1 ≤ n ≤ 10⁵) 
dp = [0]*(max_len+1) # 10⁵ +1 
d  = [0]*(max_len+1) # 10⁵

n = map(int, input()) # 
max_sg = 0 # variable que va a ir guardando la longitud de la subsecuencia de longitud máxima que es good secuence 
for elem in map(int,input().split()): # itera por cada elemento de la secuencia
    dp[elem] = d[elem] = 1

    i = 2 # empiezo i en 2 pues solo interesa buscar los divisores de elem a partir de 2
    div_elem = []
    while i*i<=elem : # busco busco los d que dividan a elem hasta las sqrt(elem) pues si d|elem  elem/d | elem tambien
        if elem % i == 0: # si i | elem
            dp[elem] = max(dp[elem], d[i] + 1 ) #
            dp[elem] = max(dp[elem], d[elem//i] + 1)
            div_elem.append(i) # agrego elem a la lista de divisores 
        i += 1 #incremento el contador en 1
    
    for i in div_elem: # se va por cada divisor de elem
        d[i] = d[elem//i] = dp[elem]
    d[elem] = dp[elem]
    max_sg= max(dp[elem], max_sg)

print(max_sg) # imprime en consola la mayor subsecuencia good sequence 

