#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int eulerphi(int n)
{
    int i,sqrtn=sqrt(n),phi=n;
    for(i=2;i<=sqrtn;i++)
    {
        if (n%i==0)
        {
            while (n%i==0) n/=i;
            phi=phi*(i-1)/i;
        }
    }
    if (n!=1) phi=phi*(n-1)/n;
    return phi;
}
signed main()
{
    int n,x;
    cin>>n; while (n--)
    {
        cin>>x; cout<<eulerphi(x)<<endl;
    }
    return 0;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgZW5kbCAiXG4iCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBldWxlcnBoaShpbnQgbikKewogICAgaW50IGksc3FydG49c3FydChuKSxwaGk9bjsKICAgIGZvcihpPTI7aTw9c3FydG47aSsrKQogICAgewogICAgICAgIGlmIChuJWk9PTApCiAgICAgICAgewogICAgICAgICAgICB3aGlsZSAobiVpPT0wKSBuLz1pOwogICAgICAgICAgICBwaGk9cGhpKihpLTEpL2k7CiAgICAgICAgfQogICAgfQogICAgaWYgKG4hPTEpIHBoaT1waGkqKG4tMSkvbjsKICAgIHJldHVybiBwaGk7Cn0Kc2lnbmVkIG1haW4oKQp7CiAgICBpbnQgbix4OwogICAgY2luPj5uOyB3aGlsZSAobi0tKQogICAgewogICAgICAgIGNpbj4+eDsgY291dDw8ZXVsZXJwaGkoeCk8PGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=

NQoxCjIKMwo0CjU=

5
1
2
3
4
5