Cho đ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 nối với điểm bằng sợi dây màu xanh, 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à 3 đ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à 3 đ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 ≤ 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~.

Giới hạn:

• Subtask 1: 30 tests có ~n \le 100~
• Subtask 2: 30 tests có ~n \le 1000~
• Subtask 3: 40 tests có ~n \le 10^6~

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.

Sample

Input #1

2
3
5

Output #1

0
1

Problem source: Kc97ble - Free Contest 19