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 gcd(a,b):
    gcd=1
    for i in range(2,min(a,b)+1):
        if a%i==0 and b%i==0:
            gcd=i
            break
    if gcd==1:
        return 0
    else:
        return 1
    
n=int(input())
l=[int(x) for x in input().split()]
ans=[]
for i in range(0,n-1):
    if l[i]%2==0:
        ans.append(l[i])
    else:
        if l[i]%2==1 and i==0:
            if gcd(l[i],l[i+1])!=0:
                ans.append(l[i])
       
        
        
        
        
        else:
            if gcd(l[i],l[i-1])!=0 and gcd(l[i],l[i+1])!=0:
                ans.append(l[i])
i+=1
if l[i]%2==1 and i==n-1:
            if gcd(l[i],l[i-1])!=0:
                ans.append(l[i])
                
if len(l)==1:
    print(1)
else: 
    
    print(len(set(ans)))
                
                
                