시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB30019516967.331%

문제

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

ㄱ-트로미노 타일은 $1 \times 1$ 블록 $3$개를 ㄱ 모양으로 이어서 붙인 도형이고 회전하여 사용할 수 있다. L-트로미노 타일링이랑 같은 것 같다고? 기분 탓이다. ㄱ-

위 그림은 $2 \times 6$ 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 100)$

테스트 케이스의 첫 번째 줄에 양의 정수 $N$이 주어진다. $(1 \le N \le 100)$

출력

테스트 케이스의 첫 번째 줄에 타일을 채우는 방법의 수를 출력한다.

예제 입력 1

2
2
3

예제 출력 1

0
2

힌트

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