HS08PAUL  A conjecture of Paul Erdős
In number theory there is a very deep unsolved conjecture of the Hungarian Paul Erdős (19131996), 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≤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:
20150201 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.


Ouditchya Sinha:
20150201 18:21:58
Great problem!!! Loved solving it. :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150201 18:21:58
my compressed precomputation fit on 4096B of source limit ;) Great Problem, thanks. 
Added by:  Robert Gerbicz 
Date:  20090405 
Time limit:  1s 
Source limit:  4096B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  High School Programming League 2008/09 