Sanggeun Trapped in a Maze

Sanggeun is trapped in a maze made of hexagonal rooms that are joined together without end. Each room is connected by doors to its six neighboring rooms, so you can move from one room to an adjacent one. Because the number of rooms is infinite, Sanggeun can never escape the maze.

Starting from the room Sanggeun is currently in, count the number of distinct paths that make exactly $n$ moves between rooms and end back at the starting room. A single move goes from the current room through a door into one of its six neighbors, and a room may be visited more than once.

The first line contains the number of test cases $T$. Each test case consists of a single line containing an integer $n$. ($1 \le n \le 14$)

For each test case, print the number of paths that correspond to the given number of moves $n$, one per line. The answer is always smaller than $2^{31}$.