I. The Silence of the Lamps
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

First, for those who have never seen a lamp before, let's say it is a cuboid (box with rectangular faces) made of glass and filled with gas. All sides of a lamp have integer lengths. Once upon a time, our lecturer was sentenced for destroying lamps on a street. He must have gone somewhat crazy, as he thought some of the lamps were screaming at him in high-pitched voices.

In his beautiful mind, he followed a weird pattern. He only recognized and destroyed those lamps which had no square face and whose volume did not exceed a fixed value. Later, during a session with his doctor Clarice, he said he was very scared of large objects and of objects with too regular shapes.

Your task is to count all possible shapes matching lecturer's conditions.

Input

The first input line contains a number $$$T$$$ of test cases ($$$1 \leq T \leq 10^5$$$). Each of the next $$$T$$$ lines contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$), the maximum recognizable volume of a lamp.

Output

For each test case output the number of different lamp shapes which could have been destroyed in the rage.

Example
Input
5
5
6
10
30
666
Output
0
1
3
26
2406