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.
### Example
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$
