CF1353C Board Moves

You are given a board of size $ n \times n $ , where $ n $ is odd (not divisible by $ 2 $ ). Initially, each cell of the board contains one figure. In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell $ (i, j) $ you can move the figure to cells: - $ (i - 1, j - 1) $ ; - $ (i - 1, j) $ ; - $ (i - 1, j + 1) $ ; - $ (i, j - 1) $ ; - $ (i, j + 1) $ ; - $ (i + 1, j - 1) $ ; - $ (i + 1, j) $ ; - $ (i + 1, j + 1) $ ; Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell. Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. $ n^2-1 $ cells should contain $ 0 $ figures and one cell should contain $ n^2 $ figures). You have to answer $ t $ independent test cases.

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 200 $ ) — the number of test cases. Then $ t $ test cases follow. The only line of the test case contains one integer $ n $ ( $ 1 \le n < 5 \cdot 10^5 $ ) — the size of the board. It is guaranteed that $ n $ is odd (not divisible by $ 2 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ ( $ \sum n \le 5 \cdot 10^5 $ ).

For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.