#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000000
#define MAXM 100
#define dd cout<<"debug"<<endl
#define pa {system("pause");}
#define p(x) printf("%d\n", x)
#define pd(x) printf("%.7lf\n", x)
#define k(x) printf("Case %d: ", ++x)
#define s(x) scanf("%d", &x)
#define sd(x) scanf("%lf", &x)
#define mes(x, d) memset(x, d, sizeof(x))
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int euler(int n)
{
    int res = n;
    int a = n;
    for(int i = 2; i * i <= a; i ++)
    {
        if(a % i == 0) 
        {
            res = res / i * (i - 1);
            while(a % i == 0) a /= i;
        }
    }
    if(a > 1) res = res / a * (a - 1);     
    return res;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T --)
    {
        scanf("%d", &n);
        printf("%d\n", euler(n + 1));
    }
    return 0;
}