#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair < int , int > pii ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 1e7 + 7 ;
const int MOD = 1000003 ;


bool comp[ MAXN ] ;
vector < int > divs[ MAXN ] ;

int eu[ MAXN ] ;

ll sm_xy[ MAXN ] , sm_x[ MAXN ] , sm_y[ MAXN ] ;
ll cnt[ MAXN ] ;

void solve ( ) {
    for ( int i = 1 ; i < MAXN ; ++ i ) {
        eu[ i ] = 1 ;
    }
    for ( int i = 2 ; i < MAXN ; ++ i ) {
        if ( comp[ i ] == true ) { continue ; }
        for ( int j = i ; j < MAXN ; j += i ) {
            if ( i != j ) { 
                comp[ j ] = true ;
            }
            int ctr = 0 ;
            int dummy = j ;
            while ( ( dummy % i ) == 0 ) {
                if ( ctr == 0 ) {
                    eu[ j ] = eu[ j ] * ( i - 1 ) ;
                }
                else {
                    eu[ j ] = eu[ j ] * i ;
                }
                ++ ctr ;
                dummy /= i ;
            }
        }
    }
    for ( int i = 1 ; i < MAXN ; ++ i ) {
        sm_x[ i ] = sm_x[ i - 1 ] + 2LL * i * eu[ i ] ;
        if ( i == 1 ) { -- sm_x[ i ] ; }
        
        sm_x[ i ] %= MOD ;
        if ( i > 1 ) {
            sm_y[ i ] = sm_y[ i - 1 ] + 2 * eu[ i ] ;
            if ( i == 1 ) { -- sm_y[ i ] ; }
        }
        else {
            sm_y[ i ] = 1 ;
        }
        ll aux = 1LL * i * i ;
        aux %= MOD ;
        aux = ( aux * eu[ i ] ) % MOD ;
        sm_xy[ i ] = sm_xy[ i - 1 ] + aux ;

        cnt[ i ] = ( cnt[ i - 1 ] + 2 * eu[ i ] ) % MOD ;
        if ( i == 1 ) { -- cnt[ i ] ; }
    }
    int q ; cin >> q ;
    while ( q -- ) {
        int x ; cin >> x ;
        if ( x == 1 ) { cout << "0\n" ; }
        else {
            int mid = ( x / 2 ) ;
            ll ans = ( cnt[ x - 1 ] * x * x ) % MOD - ( sm_y[ x - 1 ] * x ) % MOD - ( sm_x[ x - 1 ] * x ) % MOD + sm_xy[ x - 1 ] ;
            ans = ( ans + 10 * MOD ) % MOD ;
            
            ll sub = ( cnt[ mid ] * x * x ) % MOD - ( 2LL * sm_y[ mid ] * x ) % MOD - ( 2LL * sm_x[ mid ] * x ) % MOD + 4LL * sm_xy[ mid ] ;
            sub = ( sub + 10 * MOD ) % MOD ;
            ans = ( ans - sub + MOD ) % MOD ;
            ans *= 2 ;
            ans += 2 * x ;
            ans %= MOD ;
            cout << ans << "\n" ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}