不同的击打方式

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

许多易拉罐堆成一个三角形金字塔。第 $1$ 行有 $1$ 个罐，第 $2$ 行有 $2$ 个罐，依此类推。罐子按从上到下、每行从左到右的顺序依次编号为 $1^2,2^2,3^2,\ldots$。

你击中了编号为 $n^2$ 的罐。这个罐会倒下，直接堆叠在它上方的罐也会倒下；这个过程不断向上传递。请计算所有倒下罐子的编号之和。这里罐子编号 $x^2$ 的数值就是 $x\times x$。

输入格式

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

接下来 $t$ 行，每行包含一个整数 $n$，表示击中编号为 $n^2$ 的罐。

输出格式

对每个测试用例输出一行一个整数，表示所有倒下罐子的编号之和。

样例输入 1

10
9
1
2
3
4
5
6
10
1434
1000000

样例输出 1

156
1
5
10
21
39
46
146
63145186
58116199242129511

数据范围

$1\le t\le1000$，$1\le n\le10^6$。答案保证能用 64 位有符号整数表示。