#!/bin/python

import sys
import math
def choose(n,k):
    ret=1;
    for i in range (0,k):
        ret=ret*(n-i)
    return ret/math.factorial(k+1)
def answerHelper(n,k):
    totalGraphs = 0

    for s in range(1,n):
        graphs = 0
        for t in range(0,k+1):
            graphs += answer(s, t) * answer(n - s, k - t)

        graphs = choose(n, s)*s*(n - s) * graphs
        totalGraphs+= graphs

    return totalGraphs/2

F = {}
def answer(n, k):
    if (n, k) in F:
        return F[n, k]

    N = n * (n - 1)/2

    if k is n - 1:
        return int(n ** (n-2))
    if k < n or k > N:
        return 0
    if k == N:
        return 1

    result = ((N - k + 1) * answer(n, k - 1) + answerHelper(n, k - 1)) / k
    F[n, k] = result
    return result





q = int(raw_input().strip())
for a0 in xrange(q):
    n = int(raw_input().strip())
    s=0
    for k in range(n-1,((n)*(n-1))/2+1):
        s=(s%663224321+answer(n,k)%663224321)%663224321
    print(s)