타일 채우기

높이가 4, 너비가 N인 직사각형 보드를 2×1 또는 1×2 크기의 도미노로 빈칸 없이 채우려고 한다. 도미노는 서로 겹치거나 보드 밖으로 나가면 안 된다.

N이 주어질 때, 보드를 채우는 서로 다른 방법의 수를 출력하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1 이상 1,000 이하이다. 이어지는 T개의 줄에는 각 테스트 케이스의 너비 N이 하나씩 주어진다. N은 자연수이다.

각 N은 정답이 2,147,483,647 이하가 되도록 주어진다.

각 테스트 케이스마다 높이 4, 너비 N인 보드를 채우는 방법의 수를 한 줄에 하나씩 출력한다.