Goldbach Triangles

Time limit3sMemory limit512 MB

Summary

Given odd N, count the unordered triples of odd primes that sum to N and can form a triangle, for up to 100,000 queries with N up to 1,000,000.

Level: Medium7 of 10
Topics: Number theory, Prefix sum, Math
Solved: No attempts yet

Problem

Goldbach's conjecture: every even integer greater than 2 can be written as the sum of two primes.
Goldbach's weak conjecture: every odd integer greater than 5 can be written as the sum of three primes.

A representation of an odd integer $N$ as the sum of three primes is called a Goldbach triple. A Goldbach triple $(a, b, c)$ whose three primes are all odd is called a Goldbach triangle if a triangle with side lengths $a$ , $b$ , and $c$ can be formed. Given an odd integer $N$ , find the number of Goldbach triangles. Triples that differ only in the order of their primes count as the same triple.

Input

The first line contains the number of test cases $T$ (1 ≤ T ≤ 100,000). Each test case is on its own line. The integer $N$ is odd and satisfies $5 < N ≤ 1,000,000$ .

Output

For each test case, print the number of Goldbach triangles.

Examples1

Example 1
Input
```
6
11
15
41
43
993
999
```
Expected output
```
1
2
5
4
167
176
```