在嘉年华游戏中,有一个巨大的罐头金字塔,其中有 $$$2023$$$ 行,按如图所示的规则模式编号。
如果罐子$$$9^2$$$最初被击中,那么上图中所有红色的罐子都会掉落。
你向金字塔扔一个球,它击中了一个编号为 $$$n^2$$$ 的罐子。这会导致堆叠在该罐顶上的所有罐子掉落(即 $$$n^2$$$ 罐子掉落,然后直接位于 $$$n^2$$$ 上方的罐子掉落,然后直接位于这些罐子上方的罐子掉落,依此类推)。例如,上图显示,如果罐子 $$$9^2$$$ 被击中,罐子就会掉落。
掉落的所有罐子上的数字总和是多少?回想一下 $$$n^2 = n \times n$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) - 这意味着你击中的罐子有标签 $$$n^2$$$。
输出
对于每个测试用例,输出一个整数 - 所有掉落的罐子上的数字之和。
请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。对于所有有效输入,答案将始终适合 64 位整数类型。
示例
输入 #1
10 9 1 2 3 4 5 6 10 1434 1000000
输出 #1
156 1 5 10 21 39 46 146 63145186 58116199242129511
注意
第一个测试用例如声明中所示。落下的数字之和为 $$$$$$1^2 + 2^2 + 3^2 + 5^2 + 6^2 + 9^2 = 1 + 4 + 9 + 25 + 36 + 81 = 156。$$$$$$
在第二个测试用例中,只有标记为 $$$1^2$$$ 的罐头掉落,因此答案为 $$$1^2=1$$$。
在第三个测试用例中,标记为 $$$1^2$$$ 和 $$$2^2$$$ 的罐子掉落,因此答案为 $$$1^2+2^2=1+4=5$$$。
在第四个测试用例中,标记为 $$$1^2$$$ 和 $$$3^2$$$ 的罐子掉落,因此答案为 $$$1^2+3^2=1+9=10$$$。
在第五个测试用例中,标记为 $$$1^2$$$、$$$2^2$$$ 和 $$$4^2$$$ 的罐头掉落,因此答案为 $$$1^2+2^2+4^2=1+4+16=21$$$。