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
Shubham Jadhav: 2017-05-11 17:37:38

Nice Problem. AC in one go :)

Ankit: 2015-08-02 11:14:02

good one:)

[Lakshman]: 2015-02-02 14:07:51

Something strange happend with my code. My last Ac took .20s today I changes my bool arr[] to vector and its Ac in .03s

(Mitch) That's because of template specialisation.

Last edit: 2015-02-02 15:28:49
Francky: 2015-02-02 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 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
numerix: 2015-02-01 22:28:13

@gerrob: Thanks! It's fine, now.

Robert Gerbicz: 2015-02-01 18:25:14

@numerix: Sorry for my late answer, the problem opened for pypy and included other (new) languages also.

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:0.439s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:High School Programming League 2008/09