Problem B - Triangle World

Far, far away there exists a world where everything is a triangle. Even its living forms have the shape of a triangle. The beings, the planet's inhabitants, are called "trianglers". They completely worship triangles, and everything related to them. Naturally, the trianglers don't have usual square grids as we have, since they only use triangles. They use a kind of triangular grid, as we can see in the following figure.

The triangle grids of triangle world.

A triangle grid can be identified by the height of the smaller triangles, as you can see in the figure. The trianglers need to know how many triangles do the grid points form. Note that the triangles can be of different sizes. For example, in a grid of height 4, we can find 16 small triangles of size 1, but we can also find others with size 2, 3 or 4. The following figure shows some example of triangles of size 2 and 3 that we can find in a grid of height 4. But can you help the trianglers discover the total number of triangles on a grid?

Some examples of triangles found on a grid of height 4

The Problem

Given a grid of a determined height, you have to calculate the total number of different triangles that can be formed with the points of that same grid.


The first line of input will contain an integer number C, indicating the number of cases that follow (1 ≤ C ≤ 100).

The following C lines will contain each one a single integer number H, indicating the height of the triangle grid to consider in that case (1 ≤ H ≤ 1000).


For each input case you must output a single line, in the format "Height H: NUMBER_OF_TRIANGLES", indicating the height of the triangle grid and the respective total number of triangles that can be found on that grid. You can be assured that the number of triangles will be smaller than 231 and therefore will fit on a normal signed 4-byte integer.

Sample Input


Sample Output

Height 1: 1
Height 2: 5
Height 3: 13

CPUP 2007
Universidade do Porto