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: ~\{1, 2, 3, 4\}, \{1, 4, 2, 3\}, \{2, 3, 1, 4\}, \{3, 1, 2, 4\}, \{3, 4, 1, 2\}, \{4, 2, 1, 3\}~ ~\{1, 2, 4, 3\}, \{1, 4, 3, 2\}, \{2, 3, 4, 1\}, \{3, 1, 4, 2\}, \{3, 4, 2, 1\}, \{4, 2, 3, 1\}~ ~\{1, 3, 2, 4\}, \{2, 1, 3, 4\}, \{2, 4, 1, 3\}, \{3, 2, 1, 4\}, \{4, 1, 2, 3\}, \{4, 3, 1, 2\}~ ~\{1, 3, 4, 2\}, \{2, 1, 4, 3\}, \{2, 4, 3, 1\}, \{3, 2, 4, 1\}, \{4, 1, 3, 2\}, \{4, 3, 2, 1\}~

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 \ge 2~).

Output

• Gồm ~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.

Sample Input 1

2
4
3

Sample Output 1

48
3