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
talha_76: 2021-07-01 01:50:10

I got the soln now.

Last edit: 2021-07-03 07:05:33
anchord: 2021-05-03 08:41:19

got it at last :3

worrywart_ind: 2021-04-18 19:34:04

For hint: try to figure out all the possible values x^2 and x^4 are they enough to handle??

anchord: 2021-04-12 06:41:32

I cannot figure out how to solve this with sieve, someone please give me a hint

robosapien: 2020-07-03 19:38:16

100th AC :)
Easy sieve.

rohan121_kumar: 2020-05-29 20:39:31

easy

Last edit: 2020-06-04 09:16:39
shivamvermadev: 2020-04-04 12:27:44

Great Question
Finally Solved it

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

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