Đếm số cách lát hình chữ nhật ~3×n~ bằng các domino ~2×1~ (các viên domino lát phủ kín hình chữ nhật, không chờm ra ngoài, không chồng lên nhau).

Chẳng hạn với ~n = 12~ ta có nhiều cách lát, dưới đây là một trong số đó:

Input

• Dòng đầu chứa số nguyên dương ~T~ là số bộ test;
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~.

Giới hạn:

• ~T ≤ 32; n ≤ 31~

Output

• Với mỗi ~n~, in ra trên một dòng số cách lát tương ứng.

Sample

Input #1

3
1
2
3

Output #1

0
3
0

Hint

• Với ~n = 1~ hoặc ~n = 3~, không có cách nào lát được.
• Với ~n = 2~ ta có ~3~ cách lát như sau:

Problem source: Chuyên Sơn La Online Judge