#!/bin/python3

import sys
import math

def ncr(n,r):
    f = math.factorial
    return f(n) / (f(n-r)*f(r))

q = int(input().strip())
for a0 in range(q):
    n = int(input().strip())
    # your code goes here
    maxRoad=int((n*(n-1))/2)
    minRoad=n-1
    total=0
    for i in range(minRoad,maxRoad+1):
        total=total+int(ncr(maxRoad,i))
        
    print (int(total%663224321))