Description

Translated from [CERC2018] The Silence of the Lamps.

Before we begin, if you have never seen a desk lamp before, we will treat it as a cuboid made of glass (a box with rectangular faces) filled with gas. All edge lengths of the lamp are integers.

Once, one of our lecturers was convicted for vandalizing street lamps. He must have been insane, because he believed that some street lamps were screaming loudly at him.

In his mind, he followed a strange pattern of behavior. He would only recognize and destroy street lamps whose surface is not a square, and whose volume does not exceed a given value. Later, during a session with Dr. Clarice, he said that he was very afraid of large objects and objects with shapes that are too regular.

Your task is to count all possible cuboids that satisfy the lecturer’s conditions.

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain an integer $N$, the maximum volume of a street lamp that he can recognize.

Output Format

For each test case, output the number of different street lamps that would be destroyed.

5
5
6
10
30
666

0
1
3
26
2406

Hint

$1 \le T \le 10^5$, $1 \le N \le 10^6$.

Translated by ChatGPT 5