The Silence of the Lamps

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 line contains a number of test cases $t(1\le t\le 10^5)$. Each of the next $t$ lines contains a single integer $n(1\le n\le 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.

Examples