国王这次带着更多的金币来给忠诚的骑士发金币了。

第一天，骑士收到1枚金币；之后两天（第二天与第三天），每天收到2^{2}枚金币。之后三天（第四、五、六天），每天收到3^{2}枚金币。之后四天（第七、八、九、十天），每天收到4^{2}枚金币……. 这种工资发放模式会一直这样延续下去。当连续N天每天收到N^2枚金币后，骑士会在之后的连续N+1天里，每天收到{(N+1)}^{2}枚金币。 

不过国王还是需要记下帐，他需要知道，在前K天中，骑士一共获得多少枚金币。

每个测试点有多组测试数据。

输入的第一行包含一个数字t，表示测试数据的组数。

接下来t行，每行一个数字K，表示发放金币的天数。

输出有t行，每行表示骑士收到的金币数。

样例1解释 

前3天收到的金币数为1+2^{2}+2^{2}=9。

前4天收到的金币数为1+2^{2}+2^{2}+3^{2}=18。

数据范围

对于所有测试数据有：1≤t≤20,1\leq K\leq {10}^{9}。 |测试点| K≤ |特殊性质| |-----|-----|-----| |1~2| {10}^{3} |无| |3~6| {10}^{6} |无| |7~8| {10}^{9} |K=\frac{n(n+1)}{2}，其中n是正整数| |9~10| {10}^{9} |无|

2026第五届青少年编程挑战精英赛