Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Broly and His Respect

By rakibahmed · Limits 500ms, 512 MB

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.

Sample

InputOutput
5
441
2025
225
36
100

666
3321
325
45
136


Statistics

89% Solution Ratio

Being_GoromEarliest, 11M ago