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

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

hide comments
2015-02-02 00:30:10 Francky
@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 E-2-4-primes within a range [a,b] with b-a < 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.

(gerrob) OK, go ahead. Btw, in the past it was a relatively easy hspl problem, my short brute force code here solves the problem in 0.3 seconds.

(Francky) Solved ; true it's easy. I'll try to get AC with PY3.4 without precomp (if I can)... Waiting for the next step too ; thanks ;-)
Edit : Done(PAUL2) ; Many thanks ; it seems hard.

Last edit: 2015-02-03 22:41:13
2015-02-01 22:28:13 numerix
@gerrob: Thanks! It's fine, now.
2015-02-01 18:25:14 Robert Gerbicz
@numerix: Sorry for my late answer, the problem opened for pypy and included other (new) languages also.
2015-02-01 18:21:58 numerix
@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
2015-02-01 18:21:58 Ouditchya Sinha
Great problem!!! Loved solving it. :)
2015-02-01 18:21:58 (Tjandra Satria Gunawan)(曾毅昆)
my compressed precomputation fit on 4096B of source limit ;-) Great Problem, thanks.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.