小明是一个喜欢探险的小孩,有一天,他的外婆带他去了一个大小为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。
输出:
每一行测试用例包含一个答案,即所需的最小移动次数。