Proof of the Pythagorean Theorem

Time limit1sMemory limit1024 MB

Summary

Count the ordered pairs (a, b) of positive integers up to N for which the yellow square's area is an integer multiple of one blue triangle's area.

Level: Medium5 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

The Pythagorean theorem states the following.

In a right triangle, let the hypotenuse have length $c$ and the other two sides have lengths $a$ and $b$ . Then $a^2+b^2=c^2$ .

There are so many proofs of the Pythagorean theorem that they fill a whole book. Hyunmin claims that the root of them all is the method below, which is said to have been devised by Pythagoras.

Minjae, who was listening nearby, asked the following to pull Hyunmin out of his obsession with Pythagoras.

"In the figure above, $a$ and $b$ are positive integers at most $N$ . What conditions must they satisfy for the area of the yellow square to be an integer multiple of the area of one blue triangle?"

Help Hyunmin find the answer and rescue him from Pythagoras.

Input

The first line contains the number of test cases $T(1\le T\le 10^6)$ .

Each of the next $T$ lines contains one test case $N(1\le N\le 10^{18})$ .

Output

For each test case, print on its own line the number of ordered pairs $\left( a,b \right)$ that satisfy the condition.

Examples1

Example 1
Input
```
4
1
2
3
4
```
Expected output
```
1
4
5
8
```