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

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 *x*^{2}+1, where *x* is an integer. However, a weaker form of this conjecture has been proved: there are infinitely many primes of the form *x*^{2}+*y*^{4}. 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 *x*^{2}+*y*^{4} (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*≤10^{12}.

### 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 |