def get_combos(n):
	combos = [1,1,1,4,38,728,26704,1866256,251548592,
		66296291072,34496488594816,35641657548953344,
		73354596206766622208,301272202649664088951808,
		2471648811030443735290891264,
		40527680937730480234609755344896]
	if n < len(combos):
		return combos[n]
	else:
		return 1

q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	combos = get_combos(n)
	print(combos % 663224321)