F. Problem from Malinovka
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$n$$$. Find the number of ordered triples of integers $$$(x, y, z)$$$ such that $$$1 \leq x, y, z \leq n$$$, and the product $$$x \cdot y \cdot z$$$ is a perfect square$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$An integer is a perfect square if it is equal to the square of some integer.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one integer — the number of suitable triples of integers.

Example
Input
5
1
2
3
4
999990
Output
1
4
7
20
141799145052
Note

In the first test case, the only suitable triple is $$$(1, 1, 1)$$$.

In the second test case, the following triples are suitable: $$$(1, 1, 1)$$$, $$$(2, 2, 1)$$$, $$$(2, 1, 2)$$$, $$$(1, 2, 2)$$$.