#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;

const int mod = 1e6 + 3;
inline void add(int& x, int y){
	x += y;
	if(x >= mod) x -= mod;
}
const int N = 1e7;
int s[N + 1];
int ans[N + 1];
int lp[N + 1];
int phi[N + 1];
int ps[N + 1];
int duka[N + 1];

int solve(int n){
	if(n == 1) return 0;
	int res = n % mod;
	int cnt = 1 + phi[n - 1] + phi[n - 1];
	cnt %= mod;
	add(res, 1ll * cnt * (n + n - 1) % mod);
	int sub = duka[n - 1];
/*	for(int i = 2; i < n; i++){
		add(sub, ans[i]);
		add(sub, 1ll * i * (mod + phi[i] - phi[i - 1]) % mod);
	}*/
	add(sub, sub);
	add(sub, 2);
	add(res, mod - sub);
/*	for(int i = 1; i < n; i++){
		for(int j = 1; j < n; j++){
			if(__gcd(i, j) > 1) continue;
			add(res, (mod + mod + mod - i - j) % mod);
		}
	}*/
	add(res, res);
	return res;
}

int get(int x){
	return x * 1ll * (x + 1) / 2 % mod;
}
main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);

	for(int i = 1; i <= N; i++)
		phi[i] = i;
	for(int i = 2; i <= N; i++)
		if(phi[i] == i)
			for(int j = i; j <= N; j += i)
				phi[j] -= phi[j] / i;
	phi[1] = 0;
	for(int i = 2; i <= N; i++) phi[i] %= mod;
	for(int i = 2; i <= N; i++){
		if(lp[i]) continue;
		for(ll j = i; j <= N; j += i) lp[j] = i;
	}
//	cerr << "OK\n";
	ans[1] = 1;
	for(int i = 2; i <= N; i++){
		int res = 1, cnt = 0;
		int x = i;
		while(x > 1){
			int p = lp[x], cur = 1;
			cnt++;
			while(x % p == 0){
				x /= p;
				cur *= p;
			}
			if(cur == i){
				int sum = get(i);
				add(sum, mod - 1ll * p * get(i / p) % mod);
//				sum = (sum - p * 1ll * get(i / p) % mod + mod) % mod;
				ans[i] = sum;
			}else{
				res = res * 1ll * ans[cur] % mod;
			}
		}
		if(cnt > 1){
			ans[i] = res * 1ll * (1 << (cnt - 1)) % mod;
		}
	}	
	for(int i = 2; i <= N; i++){
		duka[i] = ans[i];
		add(duka[i], 1ll * i * phi[i] % mod);
		add(duka[i], duka[i - 1]);
	}
	for(int i = 1; i < N; i++) add(phi[i + 1], phi[i]);
	int T = 1;
	cin >> T;
	for(int n; T--;){
		cin >> n;
		cout << solve(n) << '\n';
	}
}