Goldbach Triple

Time limit2sMemory limit512 MB

Summary
For each odd N up to one million, count the unordered ways to write N as a sum of three primes.
Level

Medium7 of 10

Topics
Number theory, Math, Prefix sum, Brute force
Solved
No attempts yet

Problem

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

A way of writing an odd number NN as the sum of three primes is called a Goldbach triple. Given an odd number NN, count the Goldbach triples of NN. Triples that differ only in the order of the three primes are the same triple.

Input

The first line gives the number of test cases TT (1≤T≤100,0001 \le T \le 100{,}000). Each test case occupies one line and contains an integer NN that is odd and satisfies 5<N≤1,000,0005 < N \le 1{,}000{,}000.

Output

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

Examples1

  1. Example 1

    Input
    6
9
11
17
19
1929
1999
    Expected output
    2
2
4
3
2093
3105