Find the minimum sum of weightage of the triangles formed by joining the vertices of a \(n\) sided regular polygon numbered from \(1\) to \(n\) in counter-clockwise direction. Sum of the area of all the triangles must equal to the area of the polygon and
any two triangles must share a common regin.

Note :- Weightage of the triangle is the product of numbers assigned to its vertices.

Explanation:

In \(\text Fig.1\),  \(\bigtriangleup(1,4,5)\), \(\bigtriangleup(2,4,5)\) have a intersection coloured with orange while \(\bigtriangleup(1,5,6)\) and \(\bigtriangleup(2,3,4)\) do not have any common region with any triangle so \(\text fig.1\) is discarded.

In \(\text Fig.2\), if we take any two triangles then they have at lesat a small region (coloured in red) in common. And the sum of the area of triangles \(\bigtriangleup(1,3,4) \bigtriangleup(2,3,4) \bigtriangleup(3,4,5) \bigtriangleup(3,4,6) \) is equal to the area of the hexagon.

In \(\text Fig. 3\), there is no common region between any two triangles so it is also discarded.

Input

First line of the input consist a integer \(t\) denoting the number of test cases.

Next \(t\) lines contain a integer \(n\) , number of sides in a regular polygon.

Output

For each test case print a single line containing minimum sum of weightage of triangles. If not possible print \(-1\)

Constraints

\(1 <= t <= 10^5\)

\(1 <= n <= 10^7\)