33675번 - L-트로미노 타일링

문제

3ドル \times N$ 크기의 직사각형을 L-트로미노 타일로 빈칸 없이 채우는 방법의 수를 구하는 프로그램을 작성하자.

L-트로미노 타일은 1ドル \times 1$ 블록 3ドル$개를 L 모양으로 이어서 붙인 도형이고 회전하여 사용할 수 있다.

위 그림은 3ドル \times 4$ 크기의 직사각형을 채운 한 가지 방법이다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

두 번째 줄부터 각 테스트 케이스마다 하나의 줄에 양의 정수 $N$이 주어진다.

출력

각 테스트 케이스마다 3ドル \times N$ 크기의 직사각형을 채우는 경우의 수를 한 줄에 하나씩 순서대로 출력한다.

제한

• 1ドル \le T \le 100$
• 1ドル \le N \le 100$

힌트

방법의 수가 int 자료형의 범위를 초과할 수 있으므로 long long 자료형 등을 사용하는 것을 권장한다.