#include<stdio.h>
#include<bitset>
#include<string.h>
#define nr 276997
#define mod 1000007
using namespace std;

bitset <1000010> viz;
int prim[5] = {2,3,5,7,11};
int main()
{
	FILE*f = fopen("dtcsu.in", "r");
	long long x;
	char v[22];
	for (int i = 1; i <= nr; ++i)
	{
		memset(v + 1, 0, 21);
		x = 0;
		fgets(v + 1, 21, f);
		for (int j = 1; v[j]<='9'&&v[j]>='0'; ++j)
			x = x * 10 + v[j] - '0';

		viz[x % mod] = true;
	}

	int q, sol=0;
	fscanf(f, "%d\n", &q);
	for (int o = 1; o <= q; ++o)
	{
		memset(v + 1, 0, 21);
		x = 0;
		fgets(v + 1, 21, f);
		for (int j = 1; v[j] <= '9'&&v[j] >= '0'; ++j)
			x = x * 10 + v[j] - '0';
		if (viz[x%mod])
		{
			for (int d = 0; d < 5; ++d)
			{
				while (!(x % prim[d]))
				{
					x /= prim[d];
				}
			}
			if (x == 1)
				++sol;
		}
	}
	fclose(f);

	FILE*g = fopen("dtcsu.out", "w");
	fprintf(g, "%d", sol);
	fclose(g);

	return 0;
}