Goldbach Partition 2

Time limit0.5sMemory limit512 MB

Summary

For each even N up to 1,000,000, count unordered pairs of primes that sum to N.

Level: Medium4 of 10
Topics: Number theory, Prefix sum, Math, Brute force
Solved: No attempts yet

Statement

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

A representation of an even number N as the sum of two primes is called a Goldbach partition. Given an even number N, find the number of Goldbach partitions of N. Two representations that differ only in the order of the two primes count as the same partition.

Input

The first line gives the number of test cases T (1 ≤ T ≤ 100,000). Each test case occupies one line, and the integer N is even and satisfies 2 < N ≤ 1,000,000.

Output

For each test case, output the number of Goldbach partitions.

Examples1

Example 1
Input
```
5
6
8
10
12
100
```
Expected output
```
1
1
2
1
6
```