/*************

   HDU 5391

   by chty

   2016.11.4

 *************/

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int T,cnt(),prime[];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 bool isprime(int x)

 {

     for(int i=;prime[i]*prime[i]<=x&&i<=cnt;i++) if(x%prime[i]==)  return ;

     return ;

 }

 int main()

 {

     freopen("cin.in","r",stdin);

     freopen("cout.out","w",stdout);

     T=read();  prime[]=;

     for(int i=;i<=;i++)  if(isprime(i))  prime[++cnt]=i;

     while(T--)

     {

         int x=read();

         if(x==)  printf("2\n");

         else if(isprime(x))  printf("%d\n",x-);

         else printf("0\n");

     }

     return ;

 }