题目描述

Timi口渴了，所以参加了一个扔沙包赢可乐的游戏。

Timi向可乐金字塔扔一个沙包，如沙包击中编号为$n^2$的一罐可乐。这将导致位于这罐可乐上方的所有可乐倒下（即编号为$n^2$的可乐倒下，它上面直接堆叠的可乐会倒下，以此类推）。例如，如果扔中第$9^2$号可乐，倒下的可乐如图中红色所示。可乐金字塔一共有$2023$行，按照规律编号，如下图所示。

现在Timi扔中编号为$n^2$的可乐，请你帮他确定倒下的所有可乐的编号之和。

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含一个正整数$n$，表示Timi扔中的可乐的编号为$n^2$。

输出格式

对于每个测试用例，输出一个正整数，表示倒下的所有可乐的编号之和。

请注意，某些测试用例的答案可能超过32位整数类型，因此请在你的编程语言中使用64位整数类型（如C++中的long long）。对于所有有效的输入，答案将始终符合64位整数类型。

10
9
10
1
2
3
4
5
6
1000
1000000

156
146
1
5
10
21
39
46
58550832
58116199242129511

提示

【样例解释】

第一个测试用例在题面中已经给出。倒下的可乐上的编号之和为 $1^2+2^2+3^2+6^2+9^2=1+4+9+25+36+81=156$。

第二个测试用例，标号为$1^2$、$3^2$、$6^2$和$10^2$的可乐倒下，因此答案为$1^2+3^2+6^2+10^2=1+9+36+100=146$。

第三个测试用例，只有标号为$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$。

【数据范围】

对于20%数据，保证$1\leq t\leq1000,1\leq n\leq 1000$。

对于所有数据，保证$1\leq t\leq1000,1\leq n\leq 10^6$。