#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 5
using namespace std;

int n, m, tot;
bool flag, state[N][N];

bool judge(int posy, int posx)
{
                        if(state[posy][posx] || posy >= n || posx >= m)
                                                         return false;
                        return true;
}

void DFS(int cnt)
{
                 if(flag && cnt == n * m)
                 {
                                                                tot++;
                                return;
                 }

                 bool can = true;

                 for(int i = 0; i < n && can; i++)
                 {
                                for(int j = 0; j < m && can; j++)
                                {
                                                 if(state[i][j])
                                                                         continue;
                                                 else
                                                                                                                         can = false;

                                                 if(flag == false && judge(i, j + 1) && judge(i + 1, j) && judge(i + 1, j + 1))
                                                 {
                                                                                                                                                flag = true;
                                                                                                                                                state[i][j] = state[i + 1][j] = state[i][j + 1] = state[i + 1][j + 1] = true;
                                                                                DFS(cnt + 4);
                                                                                                                                                flag = false;
                                                                                                                                                state[i][j] = state[i + 1][j] = state[i][j + 1] = state[i + 1][j + 1] = false;
                                                 }
                                                 if(judge(i, j + 1))
                                                 {
                                                                                                                                                state[i][j] = state[i][j + 1] = true;
                                                                                DFS(cnt + 2);
                                                                                                                                                state[i][j] = state[i][j + 1] = false;
                                                 }
                                                 if(judge(i + 1, j))
                                                 {
                                                                                                                                                state[i][j] = state[i + 1][j] = true;
                                                                                DFS(cnt + 2);
                                                                                                                                        state[i][j] = state[i + 1][j] = false;
                                                 }
                                                                                                 state[i][j] = true;
                                                 DFS(cnt + 1);
                                                                                                 state[i][j] = false;
                                }
                 }
}

int main()
{
                int T;
                m = 4;
                scanf("%d", &T);
                while(T--)
                {
                                                tot = 0;
                                                flag = false;
                                memset(state, false, sizeof(state));
                                scanf("%d", &n);
                                DFS(0);
                                printf("%d\n", tot);
                }
                return 0;
}

广度优先遍历