#include<cstdio>

using namespace std;

int t,n,now;

int phi(long long o)
{
    long long j,now,nowans;
    now=o;
    nowans=o;
    if(o==1)return 1;
    for(j=2;j*j<=o;j++)
    if(now%j==0)
    {
                nowans-=nowans/j;
                for(;now%j==0;)
                now/=j;
    }
    if(now!=1)nowans-=nowans/now;
    return nowans;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n==1)
        {
            puts("1");
            continue;
        }
        n++;
        printf("%d\n",phi(n)); 
    }
}