SnowballSH has learned from his math teacher that a right triangle is a triangle with a $$$90^\circ$$$ angle, and a perfect square is a positive integer that is also the square of a positive integer.
Combining these ideas, SnowballSH calls a right triangle perfect if and only if
SnowballSH gives you a positive integer $$$n$$$. Please help him determine the number of non-congruent$$$^{*}$$$ perfect right triangles whose side lengths are all at most $$$n$$$.
$$${}^*$$$ Two triangles are non-congruent if and only if there exists no sequence of translation, rotation, and/or reflection that maps one triangle exactly onto the other.
Each test consists of several test cases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$), the number of test cases. The description of the test cases follows.
The only line of each test case contains a positive integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^7$$$) — the maximum side length for a triangle.
Note that there is no constraint on the sum of $$$n$$$ over all test cases.
For each test case, output a single integer — the number of non-congruent perfect triangles whose side lengths are all at most $$$n$$$.
41520100
0129
For the first test case, all three sides of the triangle must have length 1, which means the triangle cannot be a right triangle.
For the third test case, the two perfect triangles have side lengths 3–4–5 and 5–12–13. We can check that they are both right triangles, the side lengths share no common factor other than 1 for each of the triangles, and $$$\frac{3+5}{2}=4=2^2$$$, $$$\frac{5+13}{2}=9=3^2$$$ are both perfect squares. Note that 8–15–17 is not a perfect triangle because $$$\frac{8+17}{2}=12.5$$$ is not a perfect square. It can be shown that there exist no other perfect triangles with side lengths all at most 20. Therefore, the answer is 2.
