#!/bin/python3
import sys
from math import factorial

q = int(input().strip())
for a0 in range(q):
    n = int(input().strip())
    # your code goes here
    n -= 1
    m = (n ** n) % 663224321
    print(m)