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
from math import gcd


input = sys.stdin.readline
def printf(x, end='\n'):
    sys.stdout.write(str(x) + end)

def main():
    T=1
    #T=int(input())
    def solve():
        n=int(input())
        arr=list(map(int,input().split()))
        dp=[[0]*2]*(n+1)
        curr_elem=0
        for i in range(0,n):
            if gcd(arr[i],curr_elem)>1:
                dp[i+1][1]=1+max(dp[i][0],dp[i][1]) 
                curr_elem=arr[i]
                dp[i+1][0]= max(dp[i][0],dp[i][1]) 
            else:
                dp[i+1][0]=max(dp[i][0],dp[i][1])
                dp[i+1][1]=max(dp[i][0],dp[i][1])
        print(max(dp[n][1],dp[n][0]))                     
             
        
            




        




            




        


             
                                              


                



                    







                
                      





    for i in range(T):
        solve()
    pass       

        

            
        
        



if __name__ == '__main__':
    main()
		 	 	  				  	  			    			 			