#include <stdio.h>
#include <algorithm>
#define bz_num 1000000000
#define mx 1024
#define ull unsigned long long

using namespace std;

int n, mm;
int a[mx];
int sol[mx][mx], ad[mx][mx], cmmdc[mx][mx];

int gcd(int f_rez, int b)
{
	while (b)
	{
		int c = f_rez % b;
		f_rez = b;
		b = c;
	}
	return f_rez;
}

void aduna(int *vct_sum, int vct_ter[])
{
    ull i, t = 0;
    for (i = 1; i <= max(vct_sum[0], vct_ter[0]) || t; i++, t /= (ull) bz_num)
        vct_sum[i] = (t += (ull) vct_sum[i] + vct_ter[i]) % bz_num;
    vct_sum[0] = i - 1;
}


int main()
{
	freopen("indep.in","r",stdin);
	freopen("indep.out","w",stdout);
	scanf("%ld", &n);
	for (int i = 1; i <= 1000; i++)
		for (int j = 1; j <= 1000; j++)
			cmmdc[i][j] = cmmdc[j][i] = gcd(i, j);
	for (int i = 1; i <= n; i++)
		scanf("%ld", &a[i]);
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= mm; j++)
		{
			for (int k = 1; k <= ad[j][0]; k++)
				ad[j][k] = 0;
			ad[j][0] = 1;
			ad[j][1] = 0;
		}
		ad[a[i]][0] = ad[a[i]][1] = 1;		
		for (int j = 1; j <= mm; j++)
			aduna(ad[cmmdc[a[i]][j]], sol[j]);
		mm = max(mm, a[i]);
		for (int j = 1; j <= mm; aduna(sol[j], ad[j]), j++);
	}
	for (; sol[1][0]; sol[1][0]--)
		printf("%ld", sol[1][sol[1][0]]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}