#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
#define pi pair<ll, ll>
#define fi first
#define se second
//#define fi(x) (x->first)
//#define se(x) (x->second)
ll n, t, a[111], pos;
#define push(x) (a[++pos] = (x))
void solve(){
	unsigned long long ans = 0, tmp = -1;
	for(int i = 0 ; i <= n ; i++){
		ans += (tmp *= -1) * __gcd(n, 1ll * i);
	}
	cout << ans << "\n";
}
void pme(ll sz){
	pos = 0;
	for(ll i = 2 ; i <= sz / i ; i++)
		if(sz % i == 0){
			push(i);
			while(sz % i == 0)
				sz /= i;
		}
	if(sz > 1)
		push(sz);
}
ll phi(ll x){
	ll ans = x;
	for(int i = 1 ; i <= pos ; i++)
		if(x % a[i] == 0)
			ans = ans / a[i] * (a[i] - 1);
	return ans;
}
ll calc(ll g){
	if(g % 2 == 0)
		return g * phi(n / g);
	if((n / g) % 2 == 0)
		return -g * phi(n / g);
	return -g * (n / g == 1);
}
int main(){
	cin >> t;
	while(t--){
		cin >> n;
		if(n <= 100000){
			solve();
			continue;
		}
		if(n % 2 == 1){
			cout << 0 << "\n";
			continue;
		}
		unsigned long long ans = n;
		pme(n);
		ans += calc(1);
		if(n != 1)
			ans += calc(n);
		for(ll i = 2 ; i <= n / i ; i++)
			if(n % i == 0){
				ans += calc(i);
				if(i * i != n)
					ans += calc(n / i);
			}
		cout << ans << " \n";
	}
	return 0;
}
/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);

*/