- All Contests
- ProjectEuler+
- Project Euler #229: Four Representations using Squares

# Project Euler #229: Four Representations using Squares

# Project Euler #229: Four Representations using Squares

_{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 .