Lemoine's Conjecture

Time limit2sMemory limit512 MB

Summary

Count, for each odd N up to 10^6, the representations N = p + s where p is an odd prime and s is an even semiprime (product of two primes).

Level: Medium6 of 10
Topics: Number theory, Prefix sum, Math, 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.
Weak Goldbach's conjecture: every odd number greater than 5 can be written as the sum of three primes.
Lemoine's conjecture: every odd number greater than 5 can be written as the sum of one odd prime and one even semiprime. A semiprime is the product of two primes.

Given an odd number $N$ , find the number of ways to write it as the sum of one odd prime and one even semiprime.

Input

The first line gives the number of test cases $T$ ( $1 \le T \le 100{,}000$ ). Each test case consists of one line, and the integer $N$ is odd and satisfies $5 < N \le 1{,}000{,}000$ .

Output

For each test case, output the number of ways to write $N$ as the sum of one odd prime and one even semiprime.

Examples1

Example 1
Input
```
6
9
11
17
19
1929
1999
```
Expected output
```
2
2
4
2
65
30
```