#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)

//typedef __int64 LL;
typedef long long LL;
const int MAXN = 4002;
const int MAXM = 110000;
const double eps = 1e-12;
const double PI = 4.0 * atan(1.0);
const int MOD = 1000000007;


int euler(int n) {
    int m = (int)sqrt(n + 0.5);
    int ans = n;
    for(int i = 2; i <= m; i ++) if(n % i == 0) {
        ans = ans / i * (i - 1);
        while(n % i == 0) n /= i;
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

int T, n;

int main()
{
//    FIN;
    cin  >> T;
    while(T--) {
        cin >> n;
        cout << euler(n + 1) << endl;
    }
    return 0;
}