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 ≤ 106) 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 64-bit integer)

Example

Input:
3
1
2
3

Output:
1
5
13

Source limit is 500 bytes.


Added by:nha.duong
Date:2007-08-05
Time limit:1s
Source limit:500B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 ERL JS-RHINO NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Trần Huy Hưng

hide comments
2017-05-23 14:39:53
Source Code limit not fit for java!
2017-04-11 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.
Applied the formula and AC with 0.0
All that work in vain
Smh.
2017-03-10 20:18:50
formula use->(n*(n+2)*(2n+1))/8
2017-02-10 17:16:27
I got the recursive formula for this one, then 3 WAs because I pre-computed it up to 999999 instead of 1000000 :-) careful with your < vs <=.
2017-02-10 15:25:38
Used Direct formula!
2017-02-09 06:52:11
For Level 5,what is the answer? 49?
2017-02-07 14:21:57
4 hours of pen paper. 13 pages of mathematics. One simple condensed formula. Green light..
2017-01-15 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 ,
2017-01-15 06:59:10
Use long long in C or you will get Wrong Answer and
For N : Number Of Total Triangles (Giving Above 9000, to see if your data type will be able to accommodate)
9000:182300627250
9001:182361395251
9002:182422176755
9003:182482971763
9004:182543780277
9005:182604602298
9006:182665437828
9007:182726286868
9008:182787149420
9009:182848025485

2017-01-15 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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.