#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define big (int)663224321
#define ull unsigned long long
using namespace std;
int power(ull x, ull y)
{
    int res = 1;      // Initialize result
 
    x = x % big;  // Update x if it is more than or 
                // equal to p
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % big;
 
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % big;  
    }
    return res;
}
int main() {
   ios::sync_with_stdio(false);cin.tie(NULL);
int q;cin>>q;
while(q--)
{
    int n;cin>>n;
    if(n<=2)
        cout<<1<<endl;
    else if(n==3)
        cout<<4<<endl;
        else{
            ull rx=(n*(n-1))/2;
n%=big;
        int rzx=power(2,rx);
        //cout<<rzx<<" "<<n<<endl;
        //int rt=rzx*n;
       // rt%=big;
        long long rt=rzx*n;
cout<<rt<<endl;
}
}
    return 0;
}