다이아몬드 채우기

정수 $n$이 주어진다. $4n-2$개의 삼각형으로 이루어진 벨트 모양 영역을 다이아몬드 모양으로 빈틈없이 덮는 방법의 수를 구하라.

다이아몬드 모양은 삼각형 두 개로 이루어진다. 다이아몬드는 이동, 회전, 뒤집기가 가능하지만 크기를 바꿀 수는 없다. 두 덮는 방법이 다르다는 것은, 어떤 두 삼각형이 한 방법에서는 같은 다이아몬드에 덮이고 다른 방법에서는 서로 다른 다이아몬드에 덮인다는 뜻이다.

아래 그림을 참고하라. 왼쪽은 사용할 다이아몬드 모양이고 오른쪽은 채울 영역이다.

위 그림은 $n = 1, 2, 3, 4$일 때 채울 영역이다.

테스트 케이스 $t$개에 대해 각각 답을 구하라.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10^{4}$)가 주어진다.

이어지는 $t$개의 줄에는 각각 정수 $n$ ($1 \le n \le 10^{9}$)이 하나씩 주어진다.

각 테스트 케이스마다 $4n-2$개의 삼각형으로 이루어진 벨트 모양 영역을 다이아몬드로 빈틈없이 덮는 방법의 수를 출력한다. 주어진 제약에서 이 값은 $10^{18}$을 넘지 않는다.

첫 번째 테스트 케이스에는 영역을 채우는 방법이 2가지 있다.

두 번째 테스트 케이스에는 채우는 방법이 하나뿐이다.