#include<fstream>
using namespace std;

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

int n;
int a[505];
int sol[501];
bool s[501];

int rezultat;

void Read();
void Solve();
int Prim( int a, int b );
void Submultime(int lungime, int lungmax );

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 )
     {
          Submultime( 1, k+1 );
          /*
          int l = 0; 
          for( int i = 1; i <= n; ++i )
          {
               l++;
               sol[l] = a[i];
               
               if( l == k )
               {
                   sol[l+1] = 1;
                   int rez;
                   for( int j = 1; j < l; ++j )
                   {
                        rez = Prim( sol[j], sol[j+1] );
                        if( rez != 1 )
                        {
                            break;
                            ok = 0;
                        }
                   }
                   if( ok == 1 )
                   {
                   for( int j = 1; j <= l; ++j )
                        fout << sol[j] << ' ';
                   fout << '\n';
                   }
                   i = i-k+1;
                   l = 0;
                   rezultat++;
               }
          }
          */
                    
     }
     fout << rezultat;
}

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

void Submultime( int lungime, int lungmax )
{
     if( lungime == lungmax )
     {
         int ok = 1;
         for( int j = 1; j < lungime-1; ++j )
         {
              int rez = Prim( sol[j], sol[j+1] );
              if( rez != 1 )
              {
                  ok = 0;
              }
         }
         if( ok == 1 )
             rezultat++;
         return;
     }
     for( int i = 1; i <= n; ++i )
          if( !s[i] )
          {
              s[i] = true;
              sol[lungime] = a[i];
              Submultime( lungime+1, lungmax );
              s[i] = false; 
          }
}