#include<cstdio>
#include<cstdlib>
#include <cmath>
#define MAXN 50

int num = 0;

void NQueens(int n, int AB[], int cur)   // cur == current
{
    if (cur >= n)
        ++num;//说明已经枚举完毕，成立
    else
    {
        for (int i = 0; i < n; i++)//遍历新一行可能的列
        {
            int ok = 1;
            for(int j=0; j<cur; j++)//遍历已经排好的行
                if (AB[j] == i || abs(cur - j) == abs(i - AB[j]))
                {
                    ok = 0;
                    break;
                }
            if (ok)
            {
                AB[cur] = i;
                NQueens(n, AB, cur + 1);
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, AB[MAXN];
        scanf("%d", &n);
        NQueens(n, AB, 0);
        printf("%d\n", num);
        num = 0;
    }
    return 0;
}