Broly is the legendary warrior who loves his planet and always prepares himself to protect the planet from his enemies. Frieza is the warrior from another planet who is the enemy of Broly. To take the control of Broly’s planet, Frieza sends his Army to fight with Broly.

The fighters are numbered from $1$ to $N$ and each fighter comes sequentially one after another to fight with Broly. The $i^{th}$ fighter have $i$ amount of strength. After destroying $i^{th}$ fighter Broly gains $i^{3}$ of respect, and initially, Broly doesn’t have any respect. After completing the fight, Broly needs to report to his master how much respect he earned after destroying $N$ number of fighters and the total strength of Frieza’s Army. During the fight, he was able to calculate his respect after destroying each fighter but somehow he forgot that for which fighter $j$, he earned total $X$ respect.

Formally, if Broly destroys a total of $9$ fighters and his master asks him after destroying which fighter Broly gains $36$ respect then the answer will be $3$ because after destroying the $3^{rd}$ fighter Broly gains a total of $36$ respect.

There were a total of $j^{2}$ fighters in the Frieza's Army. Now, your task is to find out the total strength of the Frieza’s Army.

Input

Each test contains multiple test cases. The first line contains $t$ ($1 \leq t \leq 1000$), the number of test cases.

The only line of each test case will contain an integer $X$ ($1 \leq X \leq 10^6$) — The respect earned by Broly after destroying $j^{th}$ fighter.

Output

For each test case, output the total strength of the Frieza’s Army.