Squares Inside Square

Hello , Programmers. There is one thing that I don't like about competitive problem solving, which is - huge problem statement. The problem setters often build up a story which is not even related to the actual problem. And that is exactly the thing I am doing right now. Let's move on to the problem.

You have been given a N x N grid. You have to count the total number of different squares inside it. The sides of the square are parallel to the axes of the grid.

For example, the following 3 x 3 grid has one (3 x 3) square, four (2 x 2) squares and nine (1 x 1) squares. Total 14 squares. Only the (2 x 2) and (3 x 3) squares have been shown in the diagram.

Input

The first will contain an integer T (1 ≤ T ≤ 10000) denoting the number of test cases.

Each of the next **T lines will contain an integer N (1 ≤ N ≤ 2000000).

Output

For each test case print the answer in a new line. It is guaranteed that the answer will fit into 64-bit signed integer.

Sample

Input	Output
2 2 3	5 14