题目描述

有一个$n×n$的棋盘（$n$为奇数），一开始每个格子中都含有一个数。现在你可以进行以下操作：

一步操作指选定任意格中的恰好一个数，并将其移动到周围的八个格子中之一。也就是说，如果原来格子的坐标是$(i,j)$，那么你可以将这个数移到$(i+1,j)$$(i-1,j)$$(i+1,j+1)$$(i,j+1)$$(i-1,j+1)$$(i+1,j-1)$$(i,j-1)$$(i-1,j-1)$这八个格子中。

当然，你不能把棋子移到棋盘外。允许在一次操作后一个格子里存在多个数。

你的任务是找出操作的最小次数，使得所有的数都在一个方格内。也就是说在$(n^2-1)$个格子内都没有数，而在$1$个格子内有所有的数。

输入格式

本题有多组测试数据。

第一行一个整数$t(1<=t<=200)$，表示测试数据的组数；

接下来的$t$行，每行一个整数$n(1<=n<=5×10^5)$——棋盘的边长。保证$n$为奇数。

同时保证所有$t$个$n$的值的和不超过$5×10^5$。

输出格式

输出共$t$行，每行包含一个整数，表示每一组测试数据的答案。

样例

3
1
5
499993

0
40
41664916690999888