#include "bits/stdc++.h"
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 10 * 1000 * 1000 * 2;
// const int MAX = 100;
const int MOD = 1000 * 1000 + 3;

LL M[MAX];
LL MX[MAX];

void init()
{
	M[1] = 1;
    FOR (i,1,MAX)
    {
        if (!M[i]) continue;
        for(int j = 2*i; j<MAX; j+=i)
        {
            M[j] -= M[i];
        }
    }

	FOR (i, 1, MAX)
	{
		// M[i] = -M[i];
		MX[i] = M[i] * i;
	}

	FOR (i, 1, MAX)
	{
		M[i] += M[i-1];
		MX[i] += MX[i-1];
		M[i] %= MOD;
		MX[i] %= MOD;
	}

}

LL calc_segm(int l, int r, int n)
{
	LL c = n / l;
	LL sm = M[r] - M[l-1];
	LL smx = MX[r] - MX[l-1];

	c %= MOD;

	LL v1 = (((c * c) % MOD) * sm) % MOD;
	LL v2 = ((((c * c) % MOD) * (c + 1) % MOD) * smx) % MOD;

	v1 *= n * 2 + 1;
	v1 %= MOD;

	LL res = v1 - v2;
	res %= MOD;
	return res;
}

LL solve(int n)
{
	LL res = 0;
	LL x = 1;
	LL prev = 1;
	while (x <= n)
	{
    	LL y = n / x;
    	x = n / y + 1;
    	// cout << prev << ' ' << x - 1 << endl;
// segment [prev , x - 1]

		res += calc_segm(prev, x-1, n);
		res %= MOD;

    	prev = x;
	}
	return (res * 2) % MOD;
}


int main(int argc, char* argv[])
{
	//ios::sync_with_stdio(false); cin.tie(0);

	init();

	int q;
	scanf("%d", &q);
	FOR (i, 0, q)
	{
		int n;
		scanf("%d", &n);
		n--;
		LL res = solve(n);
		if (n != 0) res += 2 * (n + 1);
		res %= MOD;
		if (res < 0) res += MOD;
		printf("%lld", res);
		if (i != q-1) printf(" ");
	}
	printf("\n");

}