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 1\,000~

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~.