## PAUL2 - A conjecture of Paul Erdős (hard)

no tags

In number theory there is a very deep unsolved conjecture of the Hungarian Paul Erdős (1913-1996), that there exist infinitely many primes of the form x2+1, where x is an integer. However, a weaker form of this conjecture has been proved: there are infinitely many primes of the form x2+y4. You don't need to prove this, it is only your task to find the number of (positive) primes not larger than n which are of the form x2+y4 (where x and y are integers).

### Input

An integer T, denoting the number of testcases (T≤500000). Each of the T following lines contains a positive integer n, where n≤1012.

### Output

Output the answer for each n.

### Example

```Input:
6
1
2
10
9999999
500000000000
1000000000000```
```Output:
0
1
2
13175
25874902
42377120
```
`ps. my running time on Cube is 9.83 seconds. There is one input set.`
`For a much easier version of this problem see http://www.spoj.com/problems/HS08PAUL.`

 Added by: Robert Gerbicz Date: 2015-02-03 Time limit: 25s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 JS-MONKEY Resource: own