#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e6+10;

const int mod = 258280327;

bool isprime[maxn];

LL prime[maxn], primecnt, num[maxn];

LL G[maxn], T[maxn], F[maxn], S[maxn];

LL qsm(LL a, LL n){

    LL ret = 1;

    while(n){

        if(n&1) ret = ret*a%mod;

        a=a*a%mod;

        n>>=1;

    }

    return ret;

}

void pre_deal(){

    memset(isprime, true, sizeof(isprime));

    memset(num, 0, sizeof(num));

    for(int i=2; i<maxn; i++){

        if(isprime[i]){

            num[i]++;

            for(int j=i+i; j<maxn; j+=i){

                isprime[j] = false;

                num[j]++;

            }

        }

    }

    for(int i=2; i<maxn; i++){

        if(isprime[i]){

            prime[primecnt++]=i;

        }

    }

}

void INIT()

{

    pre_deal();

    G[0] = 0;

    for(int i=1; i<maxn; i++){

        G[i] = qsm(2, num[i]);

    }

    memset(T, 0, sizeof(T));

    memset(F, 0, sizeof(F));

    memset(S, 0, sizeof(S));

    for(int i=1; i<maxn; i++){

        for(int j=i; j<maxn; j+=i){

            T[j]=(T[j]+G[j/i-1])%mod;

        }

    }

    F[1] = S[1] = 1;

    for(int i=2; i<maxn; i++){

        F[i] = ((F[i-1]+2*i-1+mod)%mod-(T[i-1]%mod)+mod)%mod;

        S[i] = (S[i-1] + F[i])%mod;

    }

}

int main()

{

    INIT();

    LL n;

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%lld", &n);

        printf("%lld\n", S[n]);

    }

    return 0;

}