Triangle - MarisaOJ: Marisa Online Judge

Triangle

Time limit: 1000 ms
Memory limit: 256 MB
Given $n$ points on the plane, no three points are collinear, the points are numbered from $1$ to $n$. People connect all pairs of points $(i,j)$ with a blue or yellow string according to the principle: If $i + j$ is a prime number, then point $i$ is connected to point $j$ by a green string, otherwise if $i + j$ is not a prime number then connect with yellow string. Then one wants to investigate how many triangles there are whose three vertices are three points out of $n$ points connected by strings of the same color. Requirement: Given $n$, count the number of triangles whose three vertices are three points in $n$ points connected by strings of the same color. ### Input - The first line contains a positive integer $T$ $(T \le 10)$, which is the number of test cases. Following are $T$ lines, each line corresponding to a test case containing an integer $n$. ### Output - Consists of $T$ lines, each line containing an integer which is the number of triangles counted corresponding to the input test case. Input: ``` 2 3 5 ``` Output: ``` 0 1 ``` ### Subtask - Subtask 1 ($30 \\%$) : $n \le 100$ - Subtask 2 ($30 \\%$) : $n \le 1000$ - Subtask 3 ($40 \\%$) : $n \le 10^6$