A conjecture of Paul Erdős

Problem code: HS08PAUL

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 x²+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²+y⁴. 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²+y⁴ (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:	5s
Source limit:	4096B
Languages:	SED C99 strict C++ 4.3.2 TCL SCALA NEM PHP SCM guile LISP sbcl LISP clisp ERL TECS TEXT DOC PDF PS PERL 6 JS
Resource:	High School Programming League 2008/09