#include <cstdio>
#include <bitset>

#define NR_GOOD 276997
#define MOD1 ((1 << 22) + 1)

std::bitset<MOD1> posOk;

unsigned long long cit() {
   char lin[20];
   fgets(lin, sizeof(lin), stdin);
   unsigned long long val = 0;
   int poz = 0;
   while (lin[poz] >= '0') {
      val = val * 10 + (lin[poz++] - '0');
   }
   return val;
}

bool isGood(unsigned long long val) {
   while (val % 2) val /= 2;
   while (val % 3) val /= 3;
   while (val % 5) val /= 5;
   while (val % 7) val /= 7;
   while (val % 11) val /= 11;
   return val == 1;
}
#include <set>
std::set<unsigned long long> seen;

void genAll(FILE *f, unsigned long long num) {
   int a[5] = {2, 3, 5, 7, 11};
   if (seen.find(num) != seen.end()) {
      return;
   }
   seen.insert(num);
   fprintf(f, "%I64u\n", num);
   for (int i = 0; i < 5; i++) {
      unsigned long long valMax = 1000 * 1000 * 1000;
      valMax *= valMax;
      if (valMax / a[i] >= num) {
         genAll(f, num * a[i]);
      }
   }
}

void GenTest() {
   FILE *f = fopen("dtcsu.in", "wb");
   genAll(f, 1);
   fprintf(f, "3\n1\n3\n13\n");
   fclose(f);
}

int main() {
#ifdef WIN32
   GenTest();
#endif
   freopen("dtcsu.in", "rb", stdin);
   freopen("dtcsu.out", "wb", stdout);
   for (int i = 0; i < NR_GOOD; i++) {
      unsigned long long good = cit();
      posOk[good % MOD1] = true;
   }
   int nrSol = 0, nrQ;
   scanf("%d\n", &nrQ);
   for (int i = 0; i < nrQ; i++) {
      unsigned long long val = cit();
      if (posOk[val % MOD1] && isGood(val)) {
         nrSol++;
      }
   }
   printf("%d\n", nrSol);
   return 0;
}