#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e7 + 10;
const int MOD = (int)1e6 + 3;

int res[N];

int main(){
    fastIO;
    res[1] = 0;
    res[2] = 6;
    for(int i = 3; i < N;  i ++ ){
        res[i] = (res[i - 1] +  ((3 * i - 2) * 1ll * (i - 1)) % MOD) % MOD;
    }
    int q;
    cin >> q;
    int l;
    for(int i = 1; i <= q; i ++ ){
        cin >> l;
        cout << res[l] << "\n";
    }
    return 0;
}