#include<fstream>
using namespace std;

ifstream fin("indep.in");
ofstream fout("indep.out");

int n;
int a[505];
int sol[501];
int rezultat;

void Read();
void Solve();
int Prim( int a, int b );

int main()
{
    Read();
    if( n < 2 )
    {
        fout << 0;
    }
    else
    Solve();
    
    fin.close();
    fout.close();
    
    return 0;
}

void Read()
{
     fin >> n;
     for( int i = 1; i <= n; ++i )
          fin >> a[i];
}

void Solve()
{
     int ok = 1;
     for( int k = 2; k <= n; ++k )
     {
          int l = 0; 
          for( int i = 1; i <= n; ++i )
          {
               l++;
               /*
               if( i + l == n && l < k )
                   break;
                  */ 
               sol[l] = a[i];
               if( l == k )
               {
                   sol[l+1] = 1;
                   ok = 1;
                   for( int j = 1; j <= l; ++j )
                   {
                        int rez = Prim( sol[j], sol[j+1] );
                        if( rez != 1 )
                        {
                            break;
                            ok = 0;
                        }
                   }
               
                   i = i - (l-1);
                   l = 0;
                   rezultat++;
               }
               /*
               if( ok == 1)
                   {
                   for( int j = 1; j <= l; ++j )
                        fout << sol[j] << ' ';
                   }
               fout <<'\n';
               */
          }
                    
     }
     fout << rezultat;
}

int Prim( int a, int b )
{
    int r;
    while( b )
    {
           r = a % b;
           a = b;
           b = r;
    }
    return a;
}