Marcus is a mathematician working at the University of Waterloo. Recently, he had been playing with triangles, and as he is a magnificent mathematician, he soon discovered a powerful formula to count right triangles under a certain hypotenuse. Are you able to keep up with Marcus?

More formally, given an integer hypotenuse $h$, Marcus would like you to count the number of non-degenerate triangles with integer legs and a hypotenuse (possibly non-integral) at most $h$. In this case, a triangle is defined as an ordered pair $(a,b)$ (representing the lengths of its legs) such that $a,b\in \mathbb{Z}$ and $1\le a,b$.

Lastly, to ensure the runtime and integrity of your solution, it will be run on $T$ test cases.

Your solution will be accepted if it has a relative error of at most ${10}^{-3}$. Relative error will be determined using the following formula:

If your answer is $p$ and the correct answer is $q$, then your answer will be considered correct if

$${\displaystyle 0.999q\le p\le 1.001q}$$

It is guaranteed that the output data has exactly the correct answer.

Constraints

For all subtasks:

$T\in \{10,100\}$

$1\le h\le {10}^9$

Subtask 1 [10%]

$T=10$

$1\le h\le 10$

Subtask 2 [10%]

$T=10$

$1\le h\le 1000$

Subtask 3 [20%]

$T=10$

$1\le h\le {10}^5$

Subtask 4 [60%]

$T=100$

$1\le h\le {10}^9$

Input Specification

The first line will contain $T$, the number of test cases.

The next $T$ lines will each contain an integer, the value of $h$ for that test case.

Output Specification

Output the answer to each test case on a separate line.

Note: while the correct answer is always an integer, the float checker is used to determine if your solution is correct, so outputting a floating-point value is OK.

Sample Input

10
1
2
3
4
5
6
7
8
9
10

Sample Output

0
1
4
8
15
22
30
41
54
69

Explanation

Here are the answers for the first few test cases:

For $h=1$, there are no triangles that satisfy the requirement.

For $h=2$, the triangle that satisfies the requirement is $(1,1)$.

For $h=3$, the triangles that satisfy the requirement are $(1,2),(2,1),(2,2)$, along with the one that satisfies $h=2$.

For $h=4$, the triangles that satisfy the requirement are $(1,3),(2,3),(3,1),(3,2)$, along with the ones that satisfy $h=3$.