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 bằng sợi dây màu xanh, ngược lại nếu 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 được nối với nhau bằng các sợi dây cùng màu.

Yêu cầu: Cho số nguyên dương n. Hãy đếm số hình tam giác mà ba đỉnh được nối với nhau bằng các sợi dây cùng màu.

Dữ liệu nhập:

Một số nguyên dương n (n ≤ 10⁶).

Kết quả xuất:

Một số nguyên là số tam giác đếm được.

Ví dụ: