Cho số nguyên dương N, đếm số cách chia các số từ 1 đến 2 x N thành N nhóm, mỗi nhóm gồm hai số, sao cho hiệu hai số trong các nhóm bằng nhau.

Dữ liệu đầu vào:

• Dòng đầu tiên gồm một số nguyên dương T là số bộ test. (T ≤ 10^6)

• T dòng sau, mỗi dòng gồm một số nguyên dương N mô tả một bộ test. (N ≤ 10^6)

Kết quả: In ra kết quả gồm T dòng, mỗi dòng in kết quả của một bộ test tương ứng.

Ví dụ:

Input:

3
1
2
3

Output:

1
2
2

Giải thích:

N = 1 có 1 cách chia là: (1,2)

N = 2 có 2 cách chia là: (1,2), (3,4) và (1,3), (2,4)

N = 3 có 2 cách chia là: (1,2), (3,4), (5, 6) và (1,4), (2, 5), (3, 6)