#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair <int, int>

vector<int> pf;
void primeFactors(int n)
{
    if (n%2==0) { pf.pb(2); }
    while (n%2 == 0)
    {
        n = n/2;
    }

    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        int ct = 0;
        while (n%i == 0)
        {
            ct++;
            if (ct == 1) { pf.pb(i); }
            n = n/i;
        }
    }

    if (n > 2) {
        pf.pb(n);
    }
}

int main() {
    int x; cin >> x;

    pf.clear();
    for (int i=0; i<x; i++) {
        pf.clear();
        int a; cin >> a;
        a++;
        int org = a;
        primeFactors(a);

        for (int i=0; i<pf.size(); i++) {
            a /= pf[i];
            a *= (pf[i]-1);

        }
        cout << a << endl;
    }
}