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 Specification

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 Specification

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

Sample Test Cases

Input

5
5
6
10
30
666

Output

0
1
3
26
2406