#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<stdlib.h>
#include<vector>
#include<stack>
#include<math.h>
#define ll long long
#define inf (0x3f3f3f3f)
#define mod (1000000007)
using namespace std;

int prime[10000] = { 0,1 };

void prime_init()
{
    for (int i = 2; i*i<10000; i++)
    {
        if (!prime[i])
            for (int j = i*i; j<10000; j += i)
                prime[j] = 1;
    }
}

int is_prime(int x)
{
    int i;
    if (x % 2 == 0 && x != 2 || x<2)
        return 0;
    for (i = 3; i*i <= x; i += 2)  
        if (x%i == 0)
            return 0;
    return 1;
}

int main()
{
    prime_init();
    int T,n;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        if (n == 4) printf("2\n");
        else if (n >= 10000 && is_prime(n)) printf("%d\n", n - 1);
        else if (n<10000 && !prime[n]) printf("%d\n", n - 1);
        else printf("0\n");
    }
    return 0;
}