#!/bin/python3

import sys
from math import factorial

binomial_coefficient_cache = dict()
qq_cache = dict()


def binomial_coefficient_naive(n, k):
    d = n - k
    if d < 0:
        return 0
    return factorial(n) // factorial(k) // factorial(d)
current_binomial = binomial_coefficient_naive


def binomial_memoized(n, k):
    if (n, k) in binomial_coefficient_cache:
        return binomial_coefficient_cache[n, k]
    res = current_binomial(n, k)
    binomial_coefficient_cache[n, k] = res
    return res
binomial = binomial_memoized


gf3_cache = dict()
B_cache = dict()


def B(m):
    if m in B_cache:
        return B_cache[m]
    B_cache[m] = int(pow(2, m * (m - 1) // 2)) if m >= 2 else 1
    return B_cache[m]


def gf3(n):
    if n in gf3_cache:
        return gf3_cache[n]
    if n < 2:
        s = 1
    else:
        q = n - 1
        s = B(q + 1) - sum(binomial(q, m) * B(q - m) * gf3(m + 1)
                           for m in range(q))
    gf3_cache[n] = s
    return s

def fac(n) :
    if n in diF:
        return diF[n];
    f = 1;
    for i in range(1,n) :
        f *= i;
        diF[i] = f;
    return f;
q = int(input().strip())
for a0 in range(q):
    n = int(input().strip())
    print(gf3(n)%663224321);