Lucky decided that he would learn to play chess. The king is the most important piece in the game of chess. The king can move one square in any direction (orthogonally or diagonally). There are total eight such cells. Thus, two kings are in the attacking position, if they are located on the adjacent cells.

Now, Lucky wants to know is the number of ways one can position $$2$$ non-identical kings on a chessboard of size \(N \times N\) so that no two of them are in the attacking position.

Input format

The first line contains an integer $$T$$ denoting the number of test cases.
The first line of each test case contains an integer $$N$$ denoting the size of the chessboard.

Output format

For each test case, print the total number of ways in a new line.

Constraints

\(1 \le T \le 10000\\ 2 \le N \le 50000\)