#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int t; cin >> t;
    while(t--) {
        ll n; cin >> n;

        //Find the distinct prime factors of n
        vector<ll> factors;
        ll temp = n;
        for(ll i = 2; i*i <= n; i++) {
            if(temp % i == 0) factors.push_back(i);
            while(temp % i == 0) temp /= i;
        }
        if(temp > 1) factors.push_back(temp);

        //Compute the totient of n, which indicates the number of integers < n that are coprime with n
        //Euler's Totient Formula states that totient(n) = n * ((p1-1) / p1) * ((p2-1) / p2) * ... * ((pk-1) / pk)
        //where p1, p2, ..., pk are the distinct prime factors of n
        //We can go through each factor and multiply our answer by (p-1) / p to compute the totient

        //Keep track of the numerator and denominator of the totient formula
        ll totNum = n, totDen = 1;
        for(ll f : factors) {
            totNum *= f-1;
            totDen *= f;
        }
        //This is the final value of totient(n)
        ll totient = totNum / totDen;

        //As long as a is coprime with n, there will be no collisions between input values
        //This means that b can be any value from 0 to n-1
        //So, there are n ways to choose b and totient(n) ways to choose a
        cout << (n*totient) << '\n';
    }
}