https://www.starrycoding.com/problem/145

#include <iostream>
using namespace std;
#pragma GCC optimize(3)

#define MOD 1000000007
#define int long long
bool debug = 0;
int f[1000003];
inline 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 ^ 48);
		ch = getchar();
	}
	return x * f;
}

void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
    puts("");
	return;
}
main()
{
    cout.tie(0);
    int T;
    T = read();
    while (T--)
    {
        int n = 0, ans = 0;
        n=read();
        for (int i = 1; i <= n; i+=8)
            f[i] = 0,f[i+1]=0,f[i+2]=0,f[i+3]=0,f[i+4]=0,f[i+5]=0,f[i+6]=0,f[i+7]=0;
        for (int i = n; i; --i)
        {
            f[i] = n / i * (n / i);
            for (int j = i << 1; j <= n; j += i)
                f[i] -= f[j];
            ans += f[i] * i % MOD;
        }
        write(((ans - (n * (n + 1) >> 1)) >> 1));
    }
    return 0;
}