#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;

typedef struct _node
{
    int row;
    int col;

    int type;
}Node;

Node board[20];
int size;
int cnt;

void init(void)
{
    memset(board, 0, sizeof(Node) * 20);

    cnt = 0;
}

int isAvailable(int row, int col, int type)
{
    for (int i = 0; i < row; i++)
    {
        if (board[i].type == 1)
        {
            if (board[i].col == col)
                return 0;

            else if (abs(col - board[i].col) == abs(row - board[i].row))
                return 0;
        }
        else if (board[i].type == 2)
        {
            if (board[i].col == col)
                return 0;

            if (type == 1)
            {
                if (abs(board[i].col - col) == abs(board[i].row - row))
                {
                    return 0;
                }
            }
        }
    }

    return 1;
}

void backTracking(int queenNum, int rookNum, int level)
{
    if (level == 2 * size)
    {
        cnt = (cnt + 1) % 20130203;
        return;
    }

    for (int i = 0; i < 2 * size; i++)
    {
        if (rookNum != 0)
        {
            if (isAvailable(level, i, 2))
            {
                board[level].row = level;
                board[level].col = i;
                board[level].type = 2;
                backTracking(queenNum, rookNum - 1, level + 1);
            }
            else
                continue;
        }

        if (queenNum != 0)
        {
            if (isAvailable(level, i, 1))
            {
                board[level].row = level;
                board[level].col = i;
                board[level].type = 1;
                backTracking(queenNum - 1, rookNum, level + 1);
            }
        }
    }
}

int main(void)
{
    int testcase;
    int itx;

    cin >> testcase;

    for (itx = 0; itx < testcase; itx++)
    {
        init();

        cin >> size;

        backTracking(size, size, 0);

        cout << cnt << endl;
    }

    return 0;
}