E. TAM GIÁC MÀU
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 . Người ta nối tất cả các cặp điểm ( ) bằng sợi dây màu xanh hoặc màu vàng
theo nguyên tắc: Nếu 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 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
đ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 nguyên dương, 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.
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 ≤ 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 mỗi bộ dữ liệu vào.
Example
Input
2
3
5
Output
0
1
E. TAM GIÁC MÀU
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 i nối với điểm j 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 nguyên dương, 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.
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 ≤ 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 mỗi bộ dữ liệu vào.
Example
Input
2
3
5
Output
0
1
