#include <cstdio>
#include <bitset>
#include <unordered_set>
#include <vector>
#include <ctime>
#include <cstring>
 
using namespace std;
 
#define NR_GOOD 276997
#define MOD1 (1 << 23)
 
std::bitset<MOD1> posOk;
 
unsigned long long cit() {
   char lin[32] = {0};
   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;
}
 
unordered_set<unsigned long long> seen;
 
bool isGood(unsigned long long val) {
   while (val % 2 == 0) val /= 2;
   while (val % 27 == 0) val /= 27;
   while (val % 3 == 0) val /= 3;
   while (val % 25 == 0) val /= 25;
   while (val % 5 == 0) val /= 5;
   while (val % 7 == 0) val /= 7;
   while (val % 11 == 0) val /= 11;
   return val == 1;
   return seen.find(val) != seen.end();
}
 
void genAll(unsigned long long num) {
   int a[] = {3, 5, 7, 11};
   if (seen.find(num) != seen.end()) {
      return;
   }
   seen.insert(num);
   for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
      unsigned long long valMax = 1000 * 1000 * 1000;
      valMax *= valMax;
      if (valMax / a[i] >= num) {
         genAll(num * a[i]);
      }
   }
}
 
int main() {
   double start = clock();
   freopen("dtcsu.in", "rb", stdin);
   freopen("dtcsu.out", "wb", stdout);
   unsigned long long good;
   for (int i = 0; i < NR_GOOD; i++) {
      good = cit();
      good ^= (good >> 24);
      posOk[good % MOD1] = true;
   }
   //genAll(1);
   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);
   fprintf(stderr, "Duration: %.3f sec\n", (clock() - start) / CLOCKS_PER_SEC);
   return 0;
}