#CF4117. 嘉年华

嘉年华

题目描述

在一个嘉年华游戏中,有一个有 2023 行的大罐头金字塔,按照规则图案编号,如上图所示。

image

如果最初击中第 929^2 罐,那么图中标红的所有罐头都会倒下。

你投掷一个球到金字塔上,它击中一个编号为 n2n^2 的单个罐头。这会导致所有叠在这个罐头上的罐头都倒下(也就是说,罐头 n2n^2 倒下,然后直接在 n2n^2 上面的罐头倒下,然后在那些罐头上方的罐头,依此类推)。例如,上图显示了如果击中第 929^2 罐,将会倒下的罐头。

求所有倒下的罐头上的数字之和是多少?注意,这里 n2=n×nn^2=n×n

输入格式

第一行包含一个整数 t(1t1000)t(1≤t≤1000) ——测试用例的数量。

每个测试用例的唯一一行包含一个整数 n(1n106)n(1≤n≤10^6) ——表示你击中的罐头的标签是 n2n^2

输出格式

对于每个测试用例,输出一个整数——所有倒下的罐头上的数字之和。

请注意,对于某些测试用例,答案可能不适合 3232 位整数类型,因此您应该在编程语言中使用至少 6464 位整数类型(例如,C++ 中的 long long)。对于所有有效的输入,答案始终适合 6464 位整数类型。

测试样例

10
9
1
2
3
4
5
6
10
1434
1000000
156
1
5
10
21
39
46
146
63145186
58116199242129511

样例说明

第一个测试用例在陈述中有图示。倒下的罐头上的数字之和为:

12+22+32+52+62+92=1+4+9+25+36+81=15612+22+32+52+62+92=1+4+9+25+36+81=156

在第二个测试用例中,只有标有 1 的罐头倒下,所以答案是 11

在第三个测试用例中,标有 14 的罐头倒下,所以答案是 1+4=51+4=5

在第四个测试用例中,标有 19 的罐头倒下,所以答案是 1+9=101+9=10

在第五个测试用例中,标有 1416 的罐头倒下,所以答案是 1+4+16=211+4+16=21