TRICOUNT  Counting Triangles
We define the LEVEL of a triangle as in the following illustrative image:
Task: Your task is very easy. All you have to do is to count all triangles in the biggest one (Level N).
Input
The first line of the input contains an integer T (T ≤ 10000)  the number of test cases and T lines follow. Each line contains an integer N (1 ≤ N ≤ 10^{6}) which is the level of the triangle in that test case.
Output
For each test case, you should write a seperate line: the number of triangles in the biggest one (Level N). (All answers will fit within the range of a 64bit integer)
Example
Input:
3
1
2
3
Output:
1
5
13
Source limit is 500 bytes.
hide comments
sushanth_r:
20170411 18:16:10
Did it the way it should be done i.e by figuring out a pattern after working for 2 hours. Result? TLE.


shauryauppal:
20170310 20:18:50
formula use>(n*(n+2)*(2n+1))/8


cake_is_a_lie:
20170210 17:16:27
I got the recursive formula for this one, then 3 WAs because I precomputed it up to 999999 instead of 1000000 :) careful with your < vs <=. 

nilabja16180:
20170210 15:25:38
Used Direct formula! 

rohit9934:
20170209 06:52:11
For Level 5,what is the answer? 49?


sonudoo:
20170207 14:21:57
4 hours of pen paper. 13 pages of mathematics. One simple condensed formula. Green light.. 

narutohokage_1:
20170115 07:01:04
i again tried with fresh mind , did not saw any comments , they distract you and made you drift from your original thinking , and i never did any recursion problem , i tried this first i got the method to solve it by recursion , and then looking through that method i got how to get formula , you could derive formula , just be patient.And NEVER GIVE UP , 

narutohokage_1:
20170115 06:59:10
Use long long in C or you will get Wrong Answer and


narutohokage_1:
20170115 06:45:57
To all , please do not think that you have tried everything and finally search the internet giving yourself that excuze , i stumbled on this problem , 3 months back and then i tried it for some time , and then it was not a good start , i was not able to do so i left it , i felt it was so tough , and now after 3 months , yesterday i again tried with fresh mind , did not saw any comments , they distract you and made you drift from your original thinking , and i never did any recursion problem , i tried this first i got the method to solve it by recursion , and then looking through that method i got how to get formula , you could derive formula , just be patient.And NEVER GIVE UP , WATCH NARUTO. 

sudeep_11:
20170114 20:10:25
easy problem if you find out formula 
Added by:  nha.duong 
Date:  20070805 
Time limit:  1s 
Source limit:  500B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 ERL JSRHINO NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Trần Huy Hưng 