#include <fstream>
#define L 100005
#define ll long long
using namespace std;

ifstream F("sum.in");
ofstream G("sum.out");

ll n,x,v[L];

int main()
{
	F>>n;
	
	for( int i=2 ; i<L ; ++i)
		v[i] = i-1;
	for( int i=2 ; i<L ; ++i)
	{
		for( int j=i<<1 ; j<=L ; j+=i)
			v[j] -= v[i];
		v[i] *= i << 1;
	}

	for(int i=1;i<=n;++i)
		F>>x,G<<v[x]<<"\n";
}