#include <stdio.h>
#define NMAX 100010

long a[3][NMAX];
long b[NMAX];
int crt, prev;
long n, nr1, nr2, sol, nr2s, nr1s;

inline long cmmdc(long x, long y)
{
    long r;
    while (y) {r=x%y;x=y;y=r;}
    return x;
}

int main()
{
    freopen("pairs.in","r",stdin);
    freopen("pairs.out","w",stdout);

    long i, x, j;

    scanf("%ld", &n);

    for (i=1; i<=n; ++i)
    {
	scanf("%ld", &x);
	if (x & 1) a[2][++nr2]=x;
	else a[1][++nr1]=x;
    } 

    for (i=1; i<=nr1; ++i)
	for (j=1; j<=nr2; ++j)
	    if (cmmdc(a[1][i],a[2][j])==1) ++sol;

    while (nr2)
    {
	nr1s=nr2s=0;
    for (i=2; i<=nr2; ++i)
	if (cmmdc(a[2][1],a[2][i])!=1)
	    a[1][++nr1s]=a[2][i];
	else 
	{
	    ++sol;
	    b[++nr2s]=a[2][i];
	}
    nr1=nr1s;
    nr2=nr2s;
    for (i=1; i<=nr2; ++i) a[2][i]=b[i];
    for (i=1; i<=nr1; ++i)
	for (j=1; j<=nr2; ++j)
	    if (cmmdc(a[1][i],a[2][j])==1) ++sol; 
    }

    printf("%ld", sol);

    fclose(stdin);
    fclose(stdout);

    return 0;
}