#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    bool col[11] = {};
    bool d1[21] = {};
    bool d2[21] = {};
    int backtrack(int i, int n, bool col[], bool d1[], bool d2[])
    {
        int cnt = 0;
        if(i == (n+1))
        {
            return 1;
        }

        for(int j = 1; j <= n; j++)
        {
            if(!col[j] && !d1[n + i - j] && !d2[i + j - 1])
            {
                col[j] = d1[n + i - j] = d2[i + j - 1] = 1;
                cnt += backtrack(i + 1, n, col, d1, d2);
                col[j] = d1[n + i - j] = d2[i + j - 1] = 0;
            }
        }
        return cnt;
    }

    int totalNQueens(int n)
    {
        if(n == 1) return 1;
        return backtrack(1, n, col, d1, d2);
    }
};

int total_test;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Solution Solver;

    cin>>total_test;
    while(total_test--)
    {
        int n;
        cin>>n;
        cout<<Solver.totalNQueens(n)<<endl;
    }
}