#include <iostream>

using std::cin;
using std::cout;
using std::endl;
using std::bad_alloc;

typedef enum {QUEEN, ABLE, NOTABLE} STATE;

class Board{
private:
  STATE* m_board;
  int m_size;
  int m_result;

public:
  Board(int _size):m_size(_size), m_result(0){
    try{
      m_board = new STATE[m_size*m_size];
    }
    catch(bad_alloc e){
      e.what();
    }
  }
  ~Board(){
    delete[] m_board;
  }

  void initBoard(STATE* _board){
    for(int i = 0; i < m_size*m_size; i++){
      _board[i] = ABLE;
    }
  }

  void process(){
    for(int k = 0; k < m_size; k++){
      int depth=0;
      initBoard(m_board);
      if(m_board[k] == ABLE)
        calc(m_board, k, depth);
    }

    cout << m_result << endl;
  }

  void calc(STATE* _parent, int _pos, int &_depth){
    try{
      STATE* board = new STATE[m_size*m_size];
      int depth = _depth;
      depth++;

      for(int i = 0; i < m_size*m_size; i++){
        board[i] = _parent[i];
      }

      setQueen(board, _pos);

      for(int i = m_size*depth; i < m_size*(depth+1); i++){  
        if(board[i] == ABLE){
          calc(board, i, depth);
        }
      }

      if(countQueen(board))
        m_result++;

      delete[] board;
    }
    catch(bad_alloc e){
      e.what();
    }
  }

  void setQueen(STATE* _board, int _pos){
    int height = _pos/m_size;
    int width = _pos%m_size;

    _board[(height*m_size)+width]=QUEEN;

    //right
    for(int j = width+1; j < m_size; j++){
      _board[(height*m_size)+j] = NOTABLE;
    }
    //left
    for(int j = width-1; j >= 0; j--){
      _board[(height*m_size)+j] = NOTABLE;
    }
    // bottom
    for(int j = height+1; j < m_size; j++){
      _board[(j*m_size)+width] = NOTABLE;
    }
    // top
    for(int j = height-1; j >= 0; j--){
      _board[(j*m_size)+width] = NOTABLE;
    }
    // botleft
    for(int i = height+1, j = width-1; i < m_size; i++, j--){
      if(j < 0)
        break;
      _board[(i*m_size)+j] = NOTABLE;
    }
    // botright
    for(int i = height+1, j = width+1; i < m_size; i++, j++){
      if(j >= m_size)
        break;
      _board[(i*m_size)+j] = NOTABLE;
    }
    // topright
    for(int i = height-1, j = width+1; i >= 0; i--, j++){
      if(j >= m_size)
        break;
      _board[(i*m_size)+j] = NOTABLE;
    }
    // topleft
    for(int i = height-1, j = width-1; i >= 0; i--, j--){
      if(j < 0)
        break;
      _board[(i*m_size)+j] = NOTABLE;
    }
  }

  bool countQueen(STATE* _board){
    int count=0;

    for(int i = 0; i < m_size; i++){
      for(int j = 0; j < m_size; j++){
        if(_board[(i*m_size)+j] == QUEEN)
          count++;
      }
    }

    if(count == m_size)
      return true;
    else 
      return false;
  }
};

int main(){
  int test=0;

  cin >> test;

  while(test--){
    int size=0;

    cin >> size;

    Board board(size);

    board.process();
  }

  return 0;
}