미로에 갇힌 상근

상근이는 육각형 모양의 방이 끝없이 맞붙어 있는 미로에 갇혀 있다. 각 방은 문을 통해 인접한 여섯 개의 방과 연결되어 있어, 한 방에서 이웃한 방으로 건너갈 수 있다. 방의 개수가 무한하므로 상근이는 결코 이 미로를 빠져나갈 수 없다.

상근이가 지금 있는 방에서 출발하여 정확히 $n$번 방을 이동한 뒤 다시 처음의 방으로 돌아오는 서로 다른 경로의 수를 구하여라. 한 번의 이동은 현재 방과 문으로 연결된 여섯 개의 이웃 방 가운데 하나로 건너가는 것을 뜻하며, 같은 방을 여러 번 지나도 된다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 정수 $n$이 적힌 한 줄로 이루어진다. ($1 \le n \le 14$)

각 테스트 케이스마다, 이동 횟수 $n$에 해당하는 경로의 개수를 한 줄에 하나씩 출력한다. 정답은 항상 $2^{31}$보다 작다.