#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] + MOD * 3;
		MX[i] += MX[i-1] + MOD * 3;
		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] + MOD;
	LL smx = MX[r] - MX[l-1] + MOD;
	sm %= MOD;
	smx %= MOD;

	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 + MOD;
	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;
	}
	res *= 2;
	if (n != 0) res += 2 * (n + 1);
	res %= MOD;
	// if (res < 0) res += MOD;

	return res;
}

int gcd(int a, int b)
{
	if (b == 0) return a;
	return gcd(b, a%b);
}

LL brute(int n)
{
	n++;
	LL res = 0;
	FOR (x, 1, n)
	{
		FOR (y, 1, n)
		{
			if (gcd(x, y) == 1)
			{
				res += n - x + n - y - 1;
				res %= MOD;
			}
		}
	}
	res = res * 2;
	if (n != 1) res += 2 * n;
	res %= MOD;
	return res;
}


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

	// FOR (i, 0, 1000)
	// {
	// 	cout<<solve(10000000 - i)<<endl;
	// }
	// return 0;

	// FOR (i, 1, 10)
	// {
	// 	LL b = brute(i);
	// 	LL x = solve(i);
	// 	cout<<i<<": "<<x<<' '<<b<<' '<<(x == b ? "" : "ASDFASDF")<<endl;
	// }
	// return 0;

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

}