THỰC HÀNH

Đế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ố đó:

Dữ liệu vào:

• Dòng đầu nghi số nguyên dương T là số bộ test
• T dòng tiếp theo, mỗi dòng ghi một số nguyên dương n

Dữ liệu ra:

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

Ví dụ:

Dữ liệu vào:
3
1
2
3

Dữ liệu ra:
0
3
0

Giải thích: 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:

Giới hạn: 1 ≤ T ≤ 32, mỗi dòng có 0 ≤ n ≤ 31