#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nmax 1000000
ll n, phi[nmax + 5], T;
void init()
{
    //Ta có phi[i] = i(1 - 1/p1)(1 - 1/p2)...(1 - 1/pk)
    //Đầu tiên ta gán phi[i] = i
    for(ll i = 1; i<=nmax; i++) phi[i] = i;
    //Tiếp tục duyệt từ 2 đến nmax để tính phi[j]
    for(ll i = 2; i<=nmax; i++)
    {
        //Nếu phi[i] == i thì i là thừa số nguyên tố
        if(phi[i] == i)
        {
            //Khi đó các bội của i đều nhận i như là tsnt
            for(ll j = i; j<=nmax; j+=i)
            {
                //Vì vậy ta sẽ nhân phi[j] = phi[j]*(1 - 1/i);
                phi[j] = phi[j] - phi[j]/i;
            }
        }
    }
}
int main()
{
    init();
    cin >> T;
    while(T--)
    {
        cin >> n;
        cout << phi[n] << "\n";
    }

}