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 자료형 등을 사용하는 것을 권장한다.