#include <bits/stdc++.h>
#include<cmath>

using namespace std;

int main(){
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        long long int n;
        cin >> n;
        if(n==1){
            cout<<n<<endl;
        }
        else {
        long long int a =((n-1)*(n-2))/2;
         a=pow(2,a);
         a+=n;
         a=a%663224321;
         cout<<a<<endl;
        }
    }
    return 0;
}