F. Frontier Fortress
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Assume that there is a country $$$F$$$ and its border is a triangle bounded by three vertices, $$$A$$$, $$$B$$$, and $$$C$$$, where $$$|\overline{BC}| = a$$$, $$$|\overline{AC}| = b$$$, and $$$|\overline{AB}| = c$$$ are all integers and $$$a \leq b \leq c$$$. To protect the country from others' invasion, country $$$F$$$ wants to build three fortresses on its border, one on each side of the triangle. However, country $$$F$$$ is poor and can only afford to build two fortresses for now. Since the royals of country $$$F$$$ live at vertex $$$A$$$, they decide to build the two fortresses on side $$$\overline{AB}$$$ and $$$\overline{AC}$$$ in order to protect point $$$A$$$. More precisely, the fortresses are built at the point where the distance from it to the two other extended sides are the same so that they may reach the other two sides more quickly when there is a danger. For instance, let us focus on the fortress on side $$$\overline{AB}$$$. The distance from the fortress on side $$$\overline{AB}$$$ (which is denoted by $$$P$$$) to $$$\overleftrightarrow{BC}$$$ and to $$$\overleftrightarrow{AC}$$$ are the same.

Let the fortress on side $$$\overline{AB}$$$ be denoted by $$$P$$$ and the one on side $$$\overline{AC}$$$ by $$$Q$$$. Then, fortress $$$P$$$ and $$$Q$$$ are responsible for the area $$$\triangle APQ$$$. They have determined that the area of $$$\triangle APQ$$$ must make the ratio $$$\frac{\triangle ABC}{\triangle APQ}$$$ be an integer. Now, given an integer $$$N$$$, which is the upper limit of the length of one side of the borders, our goal is to find out the number of triples of positive integers $$$(a, b, c)$$$ where $$$1 \leq a \leq b \leq c \leq N$$$ such that the ratio $$$\frac{\triangle ABC}{\triangle APQ}$$$ is an integer.

Input

The first line contains one integer $$$t\,(1 \leq t \leq 10^5)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

In the following $$$t$$$ lines, each line contains one test case, an integer $$$N\,(1 \leq N \leq 10^6)$$$ — the upper limit of the length of one side of the borders.

Output

For each test case, output the number of valid integer triples $$$(a, b, c)$$$ that satisfies the requirements.

Example
Input
2
3
40
Output
3
53
Note

For the second test case, where $$$N = 40$$$, one of the valid triples is $$$(a, b, c) = (15, 33, 40)$$$.

When $$$(a, b, c) = (15, 33, 40)$$$, $$$\triangle ABC = 44\sqrt{29}; \triangle APQ = 22\sqrt{29}$$$. Thus, the ratio $$$\frac{\triangle ABC}{\triangle APQ} = 2 \in \mathbb{N}$$$.