#!/bin/python

import sys

def fact(n):
    if n==1 or n==0:
        return 0
    else:
        return n*fact(n-1)

q = int(raw_input().strip())
for a0 in xrange(q):
    n = int(raw_input().strip())
    a=pow(2,0.5*n*(n-1))
    print int(a%663224321)