← 返回题目列表

Codeforces · 2170/A

A. 最大邻域

中文机器翻译题面 查看原题

考虑一个 $$$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$$$)。

输出

对于每个测试用例,打印一个整数 - 网格中所有单元格的最大成本。

示例

输入
复制

5
1
2
3
4
5

输出
复制

1
9
29
56
95

注意

在第一个示例中,只有 $$$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$$$。