using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static int calcPowCombination(int n )
    {
        int result = 1;
        int k = (n*(n-1)) / 2;
        for (int i =0; i<k;i++)
            result = (result * 2)%663224321;
        return result;
    }
    static int calcRoads(int n)
    {
            int mod = 663224321;
            int sum = calcPowCombination(n);
            for (int i=n,j=1; i >1; i--,j++)
            {
                sum = sum + ((int)Math.Pow(-1,j) * i  * calcPowCombination(i-1));
                sum = sum % mod;
            }
            return sum;
        
    }
    static void Main(String[] args) {
        int q = Convert.ToInt32(Console.ReadLine());
        for(int a0 = 0; a0 < q; a0++){
            int n = Convert.ToInt32(Console.ReadLine());
            // your code goes here
            
            Console.WriteLine("{0}", calcRoads(n));
            
            
        }
    }
}