#include<bits/stdc++.h>

using namespace std;

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

int main()
{
    int n;  cin>>n;
    while(n--)
    {
        int a;  scanf("%d",&a);
        printf("%d\n",euler(a));
    }
    return 0;
}