악보 개수 세기

음을 차례로 나열해 악보를 만든다. 각 음의 높이는 낮은 음과 높은 음 두 가지뿐이고, 각 음의 길이도 짧은 음과 긴 음 두 가지뿐이다. 짧은 음은 1초, 긴 음은 2초 동안 이어진다. 악보는 다음 조건을 모두 만족해야 한다.

a) 악보 전체의 길이가 주어진 정수 $n$초이다.
b) 낮은 짧은 음의 개수와 높은 짧은 음의 개수가 같다.
c) 낮은 긴 음의 개수와 높은 긴 음의 개수가 같다.
d) 긴 음의 개수가 짧은 음의 개수 이상이다.
e) 낮은 음과 높은 음이 번갈아 나온다.
f) 첫 음은 낮은 음이다.

짝수 $n$이 주어질 때 조건을 모두 만족하는 악보가 몇 개인지 구하라. 각 음을 길이 숫자로 적으면 $n = 6$일 때 악보는 2211, 2112, 1221, 1122의 4개다. 조건 e와 f에 따라 홀수 번째 음이 낮은 음, 짝수 번째 음이 높은 음이다. $n = 8$일 때는 2222 하나뿐이다.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 10000$).
다음 $t$개의 줄에 짝수 $n$이 한 줄에 하나씩 주어진다 ($2 \le n \le 100$).

각 테스트 케이스마다 조건을 모두 만족하는 악보의 개수를 한 줄에 하나씩 출력한다. 답은 $2^{63}$보다 작다.