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

第一天，骑士收到$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}$ |无|