Cho số nguyên dương \(N\). Ta xét các hoán vị của tập \(\{1, 2, 3, \dots, N\}\).

Ví dụ: \(N = 4\) ta có các hoán vị của tập \(\{1, 2, 3, 4\}\) gồm:

Jame chọn hai hoán vị và nhận thấy rằng một số cặp hoán vị được chọn có tổng từng cặp phần tử ở vị trí tương ứng chỉ gồm các số nguyên tố. Jame gọi các cặp hoán vị có tính chất này là cặp hoán vị nguyên tố của tập \(N\) phần tử. Ví dụ cặp hoán vị \((\{2, 4, 1, 3\}, \{3, 1, 2, 4\})\) có tổng từng cặp phần tử ở vị trí tương ứng là tập \(\{5, 5, 3, 7\}\) chỉ gồm các số nguyên tố.

Yêu cầu: Cho số nguyên dương \(N\). Hãy đếm số cặp hoán vị nguyên tố của tập \(N\) phần tử.

Input

• Dòng 1: Ghi số nguyên dương \(T\) là số bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(N\) (\(N \geq 2\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi số cặp hoán vị nguyên tố của tập \(N\) phần tử tương ứng với một bộ dữ liệu đầu vào.

Example

2
4
3

48
3

2
2
3

1
3

Constraints

• Có \(50\%\) số test có \(2 < T \leq 10, N \leq 7\);
• Có \(30\%\) số test có \(T \leq 2, N \leq 8\);
• Có \(20\%\) số test có \(T \leq 10^6, N \leq 8\).