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
robosapien:
20200703 19:38:16
100th AC :)


rohan121_kumar:
20200529 20:39:31
easy Last edit: 20200604 09:16:39 

shivamvermadev:
20200404 12:27:44
Great Question


adist98:
20190505 03:09:04
Last edit: 20190505 03:43:49 

Shubham Jadhav:
20170511 17:37:38
Nice Problem. AC in one go :) 

Ankit:
20150802 11:14:02
good one:) 

[Lakshman]:
20150202 14:07:51
Something strange happend with my code. My last Ac took .20s today I changes my bool arr[] to vector 

Francky:
20150202 00:30:10
@gerrob or numerix or ?: I didn't solve this problem, but I'm sure it could be nice to set a new task where we are asked to output the sum of E24primes within a range [a,b] with ba < m (big a, m not so big). Or something better as you have some keys in hands. But maybe it's a bad idea. If it's a good idea, I'd like you to set such a task.


numerix:
20150201 22:28:13
@gerrob: Thanks! It's fine, now. 

Robert Gerbicz:
20150201 18:25:14
@numerix: Sorry for my late answer, the problem opened for pypy and included other (new) languages also. 
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 