This problem is a programming version of Problem 229 from projecteuler.net
Consider the number . It is very special, because
Similarly, we find that
In 1747, Euler proved which numbers are representable as a sum of two squares. We are interested in the numbers which admit representations of all of the following types:
where the and are positive integers.
There are such numbers that do not exceed .
How many such numbers are there that do not exceed ?
Input Format
First line of each test file contains a single integer which is the number of queries per test file. lines follow, each containing a single integer .
Constraints
- Sum of all per test file
Output Format
For each query print exactly one number that is the answer to the problem on the separate line.
Sample Input 0
2
200
10000000
Sample Output 0
1
75373
Explanation 0
The smallest very special number is .