HS08PAUL - A conjecture of Paul Erdős


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≤10000). Each of the T following lines contains a positive integer n, where n<10000000.

Output

Output the answer for each n.

Example

Input:
4
1
2
10
9999999

Output:
0
1
2
13175

hide comments
numerix: 2015-02-01 18:21:58

@gerrob (= problemsetter): After automatic change to Cube cluster, my old Python solution (using psyco) now has the top rank. I appreciate that automatized runtime recalculation without a real rejudge, so that old psyco using AC Python solutions do not change to NZEC/TLE.
BUT: As the top rank is not the right place for my solution, I would prefer to submit a fair solution that gets AC within the TL under actual conditions.
BUT: My former solution (runtime was 1.14 s on Pyramid and top rank for quite some time) cannot pass without psyco within the new Cube TL.
SO: Could you please consider to adjust the TL and/or open it for PyPy? Perhaps PyPy will do without increasing TL.

Last edit: 2015-02-01 18:24:36
Ouditchya Sinha: 2015-02-01 18:21:58

Great problem!!! Loved solving it. :)

(Tjandra Satria Gunawan)(曾毅昆): 2015-02-01 18:21:58

my compressed precomputation fit on 4096B of source limit ;-) Great Problem, thanks.


Added by:Robert Gerbicz
Date:2009-04-05
Time limit:1s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:High School Programming League 2008/09