#include<stdio.h>
__int64 phi(int n)
{
    int i,j;
    int sum=0;
    __int64 N=n;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            N=N*(i-1)/i;
            while(n%i==0) n/=i;
        }
    }
    if(n!=1)N=N*(n-1)/n;
    return N;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%I64d\n",phi(n+1));
    }
}