StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
//using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite));
Console.SetOut(writer);
//using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open));
//Console.SetIn(reader);

Solver.Solve();

Console.Out.Flush();

public static class Solver
{
    private static readonly AtCoderIO cin = new AtCoderIO();

    public static unsafe void Solve()
    {
        int T = cin.Int();

        const long MOD = 998244353L;

        List<long> inv = new() {1, 1};
        List<long> fact = new() {1};
        List<long> invfact = new() {1};

        List<long> ans = new() {0};
        long sum = 0;
        long catalan = 0;

        while (T-- > 0)
        {
            int N = cin.Int();
            if (N % 2 == 1) Console.WriteLine("0");
            else
            {
                N /= 2;
                while (fact.Count <= 2 * N)
                {
                    int x = fact.Count;
                    if (inv.Count == fact.Count)
                    {
                        inv.Add((-(MOD / x) * inv[(int)(MOD % x)]) % MOD + MOD);
                        inv[x] %= MOD;
                    }
                    fact.Add(fact[fact.Count - 1] * x % MOD);
                    invfact.Add(invfact[invfact.Count - 1] * inv[x] % MOD);
                }
                
                while (ans.Count <= N)
                {
                    long next = 3L * sum % MOD + catalan;
                    
                    next %= MOD;
                    ans.Add(next);
                    sum += next;
                    sum %= MOD;
                    int x = ans.Count - 1;
                    long c = fact[2 * x] * invfact[x] % MOD * invfact[x] % MOD * inv[x + 1] % MOD;
                    
                    catalan += c;
                    catalan %= MOD;
                }

                Console.WriteLine(ans);
            }
        }
    }
}

public sealed class AtCoderIO
{
    Queue<string> _readQueue = new Queue<string>();

    private void LoadQueue()
    {
        if (_readQueue.Count > 0) return;
        string line = Console.ReadLine();
        string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
    }

    private void Guard()
    {
        if (_readQueue.Count == 0)
        {
            throw new Exception("NO DATA TO READ");
        }
    }

    public int Int()
    {
        LoadQueue();
        Guard();
        return int.Parse(_readQueue.Dequeue());
    }

    public long Long()
    {
        LoadQueue();
        Guard();
        return long.Parse(_readQueue.Dequeue());
    }

    public string String()
    {
        LoadQueue();
        Guard();
        return _readQueue.Dequeue();
    }

    public short Short()
    {
        LoadQueue();
        Guard();
        return short.Parse(_readQueue.Dequeue());
    }

    public byte Byte()
    {
        LoadQueue();
        Guard();
        return byte.Parse(_readQueue.Dequeue());
    }

    public char Char()
    {
        LoadQueue();
        Guard();
        return char.Parse(_readQueue.Dequeue());
    }

    public double Double()
    {
        LoadQueue();
        Guard();
        return double.Parse(_readQueue.Dequeue());
    }

    public float Float()
    {
        LoadQueue();
        Guard();
        return float.Parse(_readQueue.Dequeue());
    }

    public T Read<T>()
    {
        Type type = typeof(T);
        if (type == typeof(int)) return (T)(object)Int();
        else if (type == typeof(long)) return (T)(object)Long();
        else if (type == typeof(float)) return (T)(object)Float();
        else if (type == typeof(double)) return (T)(object)Double();
        else if (type == typeof(short)) return (T)(object)Short();
        else if (type == typeof(byte)) return (T)(object)Byte();
        else if (type == typeof(char)) return (T)(object)Char();
        else if (type == typeof(string)) return (T)(object)String();
        else return default(T);
    }

    public int[] IntArray(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int();
        }

        return arr;
    }

    public int[] ZeroIndexedPermutation(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int() - 1;
        }

        return arr;
    }

    public long[] LongArray(int n)
    {
        if (n == 0) return Array.Empty<long>();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Long();
        }

        return arr;
    }

    public double[] DoubleArray(int n)
    {
        if (n == 0) return Array.Empty<double>();

        double[] arr = new double[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Double();
        }

        return arr;
    }

    public T[] ReadArray<T>(int n)
    {
        if (n == 0) return Array.Empty<T>();

        T[] arr = new T[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Read<T>();
        }

        return arr;
    }
}