#include <stdio.h>
#include <vector>
using namespace std;

#define in "sum.in"
#define out "sum.out"

int n, i, t, rest;
int j;

int S[31], G[31];
bool ok[100066];
int phi[100066];
vector<int> V;

int Solve(int t);

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &n);
    int N = 100001;
    
    for ( int i = 1; i <= N; i++ )
        ok[i] = 0, phi[i] = 0;
    
    for ( int i = 2; i <= N; i++ )
    {
        j = 2;
        while ( i*j <= N )
        {
              ok[i*j] = 1;
              j++; 
        }
    } 
    
    phi[1] = 1;
    
    for ( int i = 2; i <= N; i++ )
        if ( ok[i] == 0 )
        {
             phi[i] = i-1;
             V.push_back(i);
        }
    
    long long K, P;
    
    for ( int i = 0; i < V.size(); i++ )
    {
        K = 1;
        P = V[i];
        for ( ; P <= N; )
        {
            for ( int a = 1; a*P <= N; a++ )
            {
                if ( phi[a] == 0 ) phi[a] = Solve(a);
                if ( phi[a] != 0 ) phi[P*a] = (V[i]-1)*K*phi[a];
            }
            K = P;
            P *= V[i];
        }
    }
    
    long long unsigned G;
    unsigned q;
    for ( int i = 1; i <= n; i++ )
    {
        scanf("%u", &q);
        G = 2*q*phi[q];
        
        printf("%llu\n", G );
    }
}

int Solve(int t)
{
    int r = 0, Q = t;
    
    for ( int i = 0; V[i]*V[i] <= Q && t > 1 && i < V.size(); ++i )
    {
        if ( t % V[i] == 0 ) r+=1, S[r] = V[i]-1, G[r] = V[i];
        while ( t % V[i] == 0 ) t /= V[i];
    }
    
    if ( t > 1 ) r+=1, S[r] = t-1, G[r] = t;
    
    for ( int i = 1; i <= r; ++i )
    {
        Q /= G[i];
    }
    
    for ( int i = 1; i <= r; ++i )
    {
        Q *= S[i];
    }
    
    return Q;
}