#include <bits/stdc++.h>

using namespace std;

int main(){
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int n;
        cin >> n;
        unsigned long long des=(n*(n-1))/2;
        unsigned long long ans=1;
        for(int i=3;i<=des;i++){
            ans=(ans%663224321+(((i*(i-1))/2)%663224321)%663224321)%663224321;
        }
        cout<<ans<<endl;
    }
    return 0;
}