#include <algorithm>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <queue>

#define TEST1

using namespace std;

#define atoi(a) (a-'a')

vector < vector <int> > board;

// state = 0이면 0으로 1이면 1로 칠한다
void paint(int y, int x, int state)
{
    // (y+1,x), (y+2,x) ... (y+k,x) ... (n,x)
    for (int k = 1; y + k < board.size(); k++)
        if (state == 1)
            board[y+k][x] = 1;
        else
            board[y+k][x] = 0;

    // (y+1,x+1), (y+2,x+2) ... (y+k,x+k) ... (n,n)
    for (int k = 1; x + k < board.size() && y + k < board.size(); k++)
        if (state == 1)
            board[y+k][x+k] = 1;
        else
            board[y+k][x+k] = 0;

    // (y+1,x-1), (y+2,x-2) ... (y+k,x-k) ... (n,1)
    for (int k = 1; x - k > -1 && y + k < board.size(); k++)
        if (state == 1)
            board[y+k][x-k] = 1;
        else
            board[y+k][x-k] = 0;
}

// 현재 선택된 row에서 퀸을 놓을 수 있는지 검사한다
// 가능한 경우들이 존재하면 모든 경우를 확인한다
// 가능한 하나의 경우를 선택 후 다음 재귀 호출한다
int nqueen(int row)
{
    // 놓을 수 있는 자리가 있는지 확인
    int valid = false;
    for (int i = 0; i < board[row].size(); i++)
        if (board[row][i] == 0)
            valid = true;
    if (!valid)
        return 0;
    if (valid && row == board.size()-1)
        return 1;


    // 가능한 모든 경우 탐색
    int possible = 0;
    for (int i = 0; i < board[row].size(); i++)
    {
        if (board[row][i] == 0)
        {
            paint(row, i, 1);

            possible += nqueen(1 + row);

            paint(row, i, 0);
        }
    }

    return possible;
}

int MAIN()
{

    vector <int> res;
    int tc; cin >> tc;
    while (tc--)
    {
        int n; cin >> n;
        board = vector < vector <int> > (n, vector <int> (n) );

        res.push_back(nqueen(0) );
    }
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << endl;
    return 0;
}