#include <iostream>
#include <vector>

using namespace std;

bool comp[31625];

vector<int> v;
bool prime(int x) {
    for (int i=0; i<v.size(); i++) {
        if (x%v[i]==0 && x != v[i]) {
            return false;
        }
    }
    return true;
}
int main() {
    for (int i=2; i<=31622; i++) {
        if (comp[i]) { continue; }
        comp[i] = false;
        for (int j=i*i; j <= 31622; j+=i) {
            comp[j] = true;
        }
    }

    for (int i=2; i <= 31622; i++) {
        if (!comp[i]) {
            v.push_back(i);
        }
    }

    int tc; cin >> tc;
    for (int i=0; i<tc; i++) {
        int x; cin >> x;
        if (x == 3) { cout << 2 << endl; continue; }
        if (x == 4) { cout << 2 << endl; continue; }
        bool mark = true;

        if (!prime(x)) { cout << 0 << endl; continue;}
        cout << x-1 << endl;
    }
}