Cho \(n\) điểm trên mặt phẳng, không có ba điểm nào thẳng hàng, các điểm được đánh số từ \(1\) đến \(n\). Người ta nối tất cả các cặp điểm (\(i,j\)) bằng sợi dây màu xanh hoặc màu vàng theo nguyên tắc: Nếu \(i+j\) là số nguyên tố thì điểm \(i\) nối với điểm \(j\), ngược lại nếu \(i+j\) không phải số nguyên tố thì nối bằng sợi dây màu vàng. Sau đó người ta muốn khảo sát xem có bao nhiêu hình tam giác mà ba đỉnh là ba điểm trong \(n\) điểm được nối với nhau bằng các sợi dây cùng màu.

Yêu cầu: Cho \(n\), hãy đếm số hình tam giác mà ba đỉnh là ba điểm trong \(n\) điểm được nối với nhau bằng các sợi dây cùng màu.

Input

• Dòng đầu tiên ghi số nguyên dương \(T\) (\(T \le 10\)) là số lượng bộ dữ liệu. Tiếp đến là \(T\) dòng, mỗi dòng tương ứng với một bộ dữ liệu chứa một số nguyên \(n\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số nguyên là số tam giác đếm được tương ứng với bộ dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(40\%\) số diểm): \(n \le 10^6\).

Example

2
3
5

0
1