Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2018
The Silence of the Lamps
lamps.c, lamps.cpp, Lamps.java, lamps.py
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 ≤ T ≤ 105 ). Each of the next T lines
contains a single integer N (1 ≤ N ≤ 106), 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 Input 1
Output for Sample Input 1
5
0
5
1
6
3
10
26
30
2406
666
