#include
#include<bits/stdc++.h>
using namespace std;
void calc(vector a)
{
int x;
cin>>x;
cout<<a[x]<<endl;
}
int main() {
int n=1000001;
int a[n]={0};
for(int i=3;i<n;i+=2)
a[i]=1;
a[2]=1;
for(int i=3;i<n;i+=2)
{
if(a[i])
{
for(int j=i*i;j<n;j+=2*i)
{
a[j]=0;
}
}
}
vector<int> p;
p.push_back(0);//to start from 1st index;
cout<<p[0]<<endl;
for(int i=0;i<n;++i)
{
if(a[i])
p.push_back(i);
}
int t;
cin>>t;
while(t)
{
--t;
calc(p);
}
return 0;
}