#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int t,n, ans;
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}
void baoli(){
	unsigned long long ans = 0;
    int xishu = -1;
	for(int i = 0 ; i <= n ; i++){
		ans += (xishu *= -1) * __gcd(n, i);
	}
	printf("%lld\n",ans);
}
signed main()
{
    t = read();
    while (t--)
    {
        n = read();
        /*for (int i = 1; i <= n / i; i++)
        {
            if (n % i == 0)
            {
                ans += i * phi(n / i);
                if (n / i != i)
                    ans += (n / i) * phi(i);
            }
        }
        printf("%lld\n", ans);*/
        baoli();
    }
    return 0;
}