#!/bin/python3

import sys

def memoize(f):
    """ Memoization decorator for functions taking one or more arguments. """
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

@memoize
def binomial(n, k):
    result = 1
    for i in range(1, k + 1):
        result = result * (n - i + 1) / i
    return result

@memoize
def A001187(n):
    if(n == 0):
        return 1
    else:
        return(int(2**(n*(n - 1)/2)- sum(k*binomial(n, k)*2**((n-k)*(n-k-1)/2)*A001187(k) for k in range(1, n))/n) % 663224321)

q = int(input().strip())
for _ in range(q):
    n = int(input().strip())
    # your code goes here
    print(A001187(n))