#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define m 4

int caocao[][] = {,,,,,,,};

int go[][][] = {{{,},{,}},{{,},{,}},{{,}}};

int kind[] = {,,};

int vis[][];

int n,tmp;

void work_caocao(int x,int y)

{

    int tmpx,tmpy;

    for(int i = ; i < ; i++)

    {

        tmpx = x + caocao[i][];

        tmpy = y + caocao[i][];

        vis[tmpx][tmpy] = ;

    }

}

bool ok(int x,int y,int k)

{

    for(int i = ; i < kind[k]; i++)

    {

        int tmpx,tmpy;

        tmpx = x+go[k][i][],tmpy = y+go[k][i][];

        if(vis[tmpx][tmpy]) return false;

        if(tmpx > n || tmpy > m) return false;

        if(tmpx <= || tmpy <= ) return false;

    }

    return true;

}

void set_vis(int x,int y,int k,int v)

{

    for(int i = ; i < kind[k]; i++)

    {

        int tmpx,tmpy;

        tmpx = x+go[k][i][],tmpy = y+go[k][i][];

        vis[tmpx][tmpy] = v;

    }

}

void dfs(int x,int y)

{

    if(y == m+)

    {

        x++;

        y = ;

    }

    if(x == n+)

    {

        tmp++;

        return;

    }

    if(vis[x][y])dfs(x,y+);

    for(int i = ; i < ; i++)

    {

        if(ok(x,y,i))

        {

            //cout<<x << "  "<<y<<endl;

            set_vis(x,y,i,);

            dfs(x,y+);

            set_vis(x,y,i,);

        }

    }

}

void set_caocao(int x,int y)

{

    for(int i = x; i < n; i++)

        for(int j = y; j < m; j++)

        {

            memset(vis,,sizeof(vis));

            //cout<<i<<"  "<<j<<endl;

            work_caocao(i,j);

            dfs(,);

        }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int ans[];

        ans[] = ,ans[] = ;

        for(int i = ;i <= ;i++)

        {

            n = i;

            tmp = ;

            set_caocao(,);

            ans[i] = tmp;

        }

        int nn;

        scanf("%d",&nn);

        printf("%d\n",ans[nn]);

    }

}