#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;
ifstream fi("sohh.inp");
ofstream fo("sohh.out");
int n,a[100000],mx = 0;
bool kt[10000000];
doc()
{
    fi >> n;
    for (int i = 0; i < n; i++)
    {
        fi >> a[i];
        mx = max(mx,a[i]);
    }
    return 0;
}

bool nt(int p)
{
    if (p < 2) return false;
    for (int o = 2; o*o <= p; o++)
       if (p%o == 0) return false;
    return true;
}

sohh()
{
   int i = 2,l = 0;
   while (l <= mx)
   {
      if (nt(i))
      {
         l = pow(2,i-1) * (pow(2,i) - 1);
         if (l <= mx) kt[l] = false;
      }
      if (i == 2) i++;
      else i += 2;
    }
   return 0;
}
per()
{
    doc();
    sohh();
    for (int i = 0; i < n; i++)
    {
       if (kt[a[i]] == false) fo << a[i] << endl;
    }
    return 0;
}

main ()
{
    fill(kt,kt+10000000,true);
    per();
	return 0;
}
