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>).
def isEmpty(p):
    return len(p) == 0
def topo(p):
    return p[-1]
def imprime(p,x):
    for i in x:
        print(p[i], end=" ")
    print()


from math import gcd
n = int(input())
a = input().split(" ")
a = map(int, a)
a = list(a)

p = [] #pilha

#estritamente crescente
#adjacentes não são coprimos, gcd(x,x+1) > 1
#todos os elementos são good integers

#encontrar o comprimento da maior good sequence
count = 0
maximo = 0

i = 0

while i < n:
    if isEmpty(p):
        p.append(i)
        #print(p)
        #imprime(a,p)
    elif gcd(a[topo(p)], a[i]) > 1:
        p.append(i)
        #print(p)
        #imprime(a,p)
    maximo = max(maximo, len(p))
    if i < n-1:
        i += 1
    elif not isEmpty(p):
        i = p.pop() + 1
        if i >= n and not isEmpty(p):
            i = p.pop() + 1



print(maximo)
