#include <bits/stdc++.h>
using namespace std;

int countSplits(vector<int> &arr){
	int n= arr.size();
	
	 vector<int> pgcd(n);
      vector<int> sgcd(n);
      
       pgcd[0]= arr[0];
           for (int i=1;i<n;i++){
            pgcd[i]=__gcd(pgcd[i-1],arr[i]);
        }
        
         sgcd[n-1]=arr[n-1];
        for(int i=n-2;i>=0;i--){
            sgcd[i]=__gcd(sgcd[i+1],arr[i]);
        }
        
        int count =0;
        
        for(int i=0;i<n-1;i++){
        	if(pgcd[i]==sgcd[i+1])
        	count++;
        }
        return count;
}

int main() {
	// your code goes here
	int n;
	cin>>n;
	
	vector<int>nums(n);
	for(int i=0;i<n;i++){
		cin>>nums[i];
	}
	
	vector<int> pgcd(n);
	pgcd[0]=nums[0];
	
	for(int i=1;i<n;i++){
		pgcd[i]=__gcd(pgcd[i-1],nums[i]);
	}
	
	vector<int> sgcd(n);
	sgcd[n-1]=nums[n-1];
	
	for(int i = n-2; i>=0;i--){
		sgcd[i]=__gcd(sgcd[i+1],nums[i]);
	}
	
	int ans = countSplits(nums);
	
	// Find arrow position
	for (int i=0;i<n;i++){
		bool arrow = false;
		
		if(i>0 && pgcd[i]!=pgcd[i-1])
		arrow = true;
		
		if(i<n-1 && sgcd[i]!=sgcd[i+1])
		arrow = true;
		
		if(arrow==true){
			vector<int>temp;
			
			for( int j=0;j<n;j++){
				if(j!=i)
				temp.push_back(nums[j]);
			}
			ans= max(ans, countSplits(temp));
		}
		
	}
	cout<<ans<<endl;
	
	return 0;
}