#include <bits/stdc++.h>

const int N = 1e7 + 50;
const int mod = 1e6 + 3;
const int inv2 = (mod + 1) / 2;
inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline auto mul(const auto &x, const auto &y) { return (int)(1ll * x * y % mod); }

inline auto mul(const auto x, const auto ... y) {
	return mul(x, mul(y...));
}

inline void upd(int &x, int y) { x = inc(x, y); }
inline void dpu(int &x, int y) { x = dec(x, y); }
inline void pud(int &x, int y) { x = mul(x, y); }

int mu[N], phi[N], pri[N], tot, f[N], sf[N], sg[N], sphi[N];
bool np[N];

void init(int n) {
	mu[1] = 1; np[1] = true; phi[1] = 1;
	f[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!np[i]) {
			pri[++tot] = i;
			mu[i] = -1;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= tot && i * pri[j] <= n; ++j) {
			np[i * pri[j]] = true;
			if (i % pri[j] == 0) {
				mu[i * pri[j]] = 0;
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			}
			else {
				mu[i * pri[j]] = -mu[i];
				phi[i * pri[j]] = phi[i] * phi[pri[j]];
			}
		}
		f[i] = mul(mul(inv2, phi[i]), i);
	}
	for (int i = 1; i <= n; ++i) {
		sphi[i] = inc(sphi[i - 1], phi[i]);
		sf[i] = inc(sf[i - 1], f[i]);
		sg[i] = inc(sg[i - 1], mul(i, f[i]));
	}
}

int solve(int n) {
	if (n == 1) return 0;
	int X = mul(n, n, sphi[n - 1]);
	dpu(X, mul(3, n, sf[n - 1]));
	upd(X, sg[n - 1]);
	upd(X, n);
	dpu(X, mul(n, n, sphi[n / 2]));
	upd(X, mul(6, n, sf[n / 2]));
	dpu(X, mul(4, sg[n / 2]));
	dpu(X, mul(2, n));
	int Y = mul(2, X);
	dpu(Y, mul(2, n));
	upd(Y, 3);
	pud(Y, 2);
	upd(Y, mul(2, n));
	return Y;
}

int main() {
	init(1e7);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int q;
	std::cin >> q;
	while (q--) {
		int x;
		std::cin >> x;
		std::cout << solve(x) << '\n';
	}
	return 0;
}