시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 29 19 17 77.273%

문제

상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다른 방으로 건너갈 수 있다. 하지만, 방의 개수는 무한대이기 때문에, 상근이는 절대 이 미로를 빠져나갈 수 없다.

오른쪽 그림에 상근이가 있는 방이 표시되어 있다. 이 때, 상근이가 있는 방에서 시작해서 방을 n번 이동해서, 다시 원래 있던 방으로 돌아오는 경로의 수를 구하려고 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 n을 포함하는 한 줄로 이루어져 있다. (1 ≤ n ≤ 14)

출력

각 테스트 케이스에 대해서, 입력으로 주어진 n에 해당하는 경로의 개수를 출력한다. 정답은 항상 231보다 작다.

예제 입력

2
2
4

예제 출력

6
90

힌트