Cho số nguyên tố lẻ \(p\).
Gọi \(A\) là tập hợp gồm các số nguyên liên tiếp từ \(1\) đến \(2 \cdot p\). Hay \(A = \{1, 2, \dots, 2 \cdot p\}\).
Một bộ gồm \(p\) số nguyên (khác nhau từng đôi một) được lấy từ tập \(A\) được gọi là bộ \(p\) "bất ngờ" nếu tổng tất cả các phần tử của bộ số đó chia hết cho \(p\).

Yêu cầu: Cho số nguyên tố \(p\). Hỏi có bao nhiêu bộ \(p\) "bất ngờ" khác nhau được tạo thành. (Hai bộ \(A\) và \(B\) được coi là khác nhau nếu tồn tại phần tử \(k\) thỏa mãn \(k \in A\) và \(k \notin B\)).

Input

• Dòng thứ nhất chứa số \(T\) (\(1 \le T \le 100\)) - thể hiện số lượng bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên tố \(p\) (\(3 \le p \le 1000\)).

Output

• Ứng với mỗi bộ dữ liệu, in ra đáp án cần tìm.

Example

1
3

8