考虑一个 $$$n \times n$$$ 网格,其中填充了如下数字:
- 第一行从左到右包含从 $$$1$$$ 到 $$$n$$$ 的整数;
- 第二行从左到右包含从$$$(n+1)$$$到$$$2n$$$的整数;
- 此模式一直持续到第 $$$n$$$ 行,其中包含从左到右从 $$$(n^2-n+1)$$$ 到 $$$n^2$$$ 的整数。
让我们将单元格的成本定义为其值加上其相邻单元格值的总和。如果两个单元共享一侧,则它们被认为是相邻的。
您的任务是计算网格中所有单元格的最大成本。
$$$n = 4$$$ 的网格及其最佳答案。黄色单元格具有最大可能的成本;绿色单元格是它的邻居。电池的成本为$$$15+11+14+16=56$$$。 输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。
输出
对于每个测试用例,打印一个整数 - 网格中所有单元格的最大成本。
示例
输入复制
512345
输出复制
19295695
注意
在第一个示例中,只有 $$$1$$$ 单元格的成本为 $$$1$$$。
在第二个示例中,值为 $$$4$$$ 的单元格具有最大成本:$$$4 + 2 + 3 = 9$$$。
在第三个示例中,值为 $$$8$$$ 的单元格具有最大成本:$$$8 + 5 + 7 + 9 = 29$$$。
在第四个示例中,值为 $$$15$$$ 的单元格具有最大成本:$$$15 + 11 + 14 + 16 = 56$$$。
在第五个示例中,值为 $$$19$$$ 的单元格具有最大成本:$$$19 + 14 + 18 + 20 + 24 = 95$$$。