#include<cstdio>
#include<cstring>
#include<cmath>

int zs[100001], cnt;
bool Z[100001];

void calc()
{
    memset(Z, 1, sizeof(Z));
    for(int i = 2; i <= 1000; i++)
    {
        int o = i * 2;
        while(o <= 100000) Z[o] = 0, o += i;
    }
    cnt = 0;
    for(int i = 2; i <= 100000; i++) if(Z[i]) zs[++cnt] = i;
}
int main()
{
    calc();
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++)
    {
        int s;
        scanf("%d", &s);
        if(s == 1)printf("1\n");
        else if(s == 4) printf("2\n");
        else{
            int j;
        for(j = 1; j <= cnt; j++)
        {
            if(zs[j] > sqrt(s)) break;
            if(s % zs[j] == 0)
            {
                printf("0\n");
                break;
            }
        }
        if(zs[j] > sqrt(s)) printf("%d\n", s - 1);}
    }
    return 0;
}