[DSA-QuayLui-NhanhCan].Bài toán N quân hậu.

Cho một bàn cờ vua có kích thước n * n, ta biết ràng quân hậu có thể di chuyển theo chiều ngang, dọc, chéo. Vấn đề đặt ra rằng, có n quân hậu, bạn cần đếm số cách đặt n quân hậu này lên bàn cờ sao cho với 2 quân hậu bất kì, chúng không ăn nhau.

Input Format

Dòng đầu ghi số bộ test T (T<=5). Mỗi bộ test ghi một số nguyên dương n duy nhất (không quá 10).

Constraints

.

Output Format

Ghi kết quả mỗi bộ test trên một dòng. Số cách đặt quân hậu.

Ví dụ:

Dữ liệu vào

1
4

Dữ liệu ra

2