宝藏男孩
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

       小明是一个喜欢探险的小孩,有一天,他的外婆带他去了一个大小为n×n网格的森林里,其中n是奇数(不能被2整除),每个格子中,都放有一个宝藏,他想把这些宝藏都集中到同一个单元格中。但是,小明正沉迷于探险小说,所以想请你帮帮他。你的任务是找到所有宝藏进入一个单元格(即n2-1单元格应该包含0个宝藏,而一个单元格应该包含n2图形)所需的最小移动次数。

       在一次移动中,你可以选择某个单元格中的一个宝藏,并将其移动到与当前单元格共享边或角的单元格中,也就是说,从单元格(i,j)你可以将其中的宝藏移动到以下单元格中:

·        (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);

       另外,你还需注意:
            第一:你不能将宝藏移出森林。
            第二:一个网格中存放多个宝藏是被允许的。



输入描述:

输入:

第一行输入一个整数t (1≤t≤200),表示测试用例的数量。接下来的t行每行包含一个整数n (1≤n<5*105)表示网格规模。题目保证n全为奇数且所有测试用例中n的总和不超过5*105,即∑n≤5*105

输出描述:

输出:

每一行测试用例包含一个答案,即所需的最小移动次数。

示例1

输入

复制
3
1
5
499993

输出

复制
0
40
41664916690999888