#include <cstdio>
#include <cmath>

using namespace std;

long long descompunere(long long n){
	long long lim,d,nr,e;
	d=2;
	nr=n;
	lim=(long long)sqrt((double)n);
	while(d<=lim&&n>1){
		e=0;
		while(n%d==0){
			e++;
			n=n/d;
		}
		if(e>0){
			nr=nr/d*(d-1);
		}
		d++;
	}
	if(n>1){
		nr=nr/n*(n-1);
	}
	return nr;
}

int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
    int a;
    scanf("%d",&a);
	long long n;
    for(int i=0;i<a;i++){
	scanf("%lld",&n);
        printf("%lld\n",(n*(n-1)/2)-(descompunere(n)*n/2));}
	return 0;
}