시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 520 320 238 60.870%

문제

4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. 예를 들어 4*2 타일을 채우는 방법은 다음과 같이 5가지가 있다.

N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다.

출력

각 테스트 케이스에 대해 4*N크기의 타일을 채우는 방법의 경우의 수를 출력한다.

예제 입력

3
2
3
7

예제 출력

5 
11 
781

힌트

N제한은 딱히 정해져있지 않다. 하지만, 4*N을 채우는 경우의 수가 int 범위 안에 들어오는 N만 주어진다.