#include <stdio.h>
#define MAXX 200000

long long phi[MAXX + 1];
int main () {
    FILE *fin , *fout;
    int n , i , j , pi , x;

    for ( i = 1 ; i <= MAXX ; i++ )
        phi[i] = 1;
    for ( i = 2 ; i <= MAXX ; i++ ) {
        if ( phi[i] == 1 ) {
            pi = 1;
            for ( j = i ; j <= MAXX ; j = j + i )
                phi[j] = phi[j] * ( i - 1 );
            while ( pi <= MAXX / i ) {
                pi = pi * i;
                for ( j = pi ; j <= MAXX ; j = j + pi )
                    phi[j] = phi[j] * i;
            }
        }
    }


    fin = fopen ( "sum.in" , "r" );
    fscanf ( fin , "%d" , &n );
    fout = fopen ( "sum.out" , "w" );

    for ( i = 0 ; i < n ; i++ ) {
        fscanf ( fin , "%d" , &x );
        fprintf ( fout , "%lld\n" , phi[2 * x] );
    }
    fclose ( fin );
    fclose ( fout );
    return 0;
}