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.


hide comments
pratikshit: 2017-10-22 08:50:36

only knowing the formula is enough for AC

anshul2222: 2017-09-21 16:48:05

having tle
any idea?

zaid9910: 2017-09-15 17:30:54

@shauryauppal This formula is not passing all the test cases.

anshul0311: 2017-08-10 21:26:09

Can anyone help in deriving this formula ?

jha_gaurav98: 2017-07-27 04:34:49

I haven't even understood how to draw the triangle of level 3

jha_gaurav98: 2017-07-27 04:32:36

how did you all got the formula?? some derivation or what?

babur: 2017-07-02 05:41:53

100% maths....good question

mukesh3g: 2017-06-24 16:26:42

Last edit: 2017-06-24 22:33:15
love1024: 2017-06-15 11:53:28

Lots of formulas of triangular number to derive.

Last edit: 2017-06-15 11:53:44
rishabhm123: 2017-05-30 00:05:57

All test cases are getting right..
As mentioned above by @narutohokage_1 in orders of 9000.
Still getting WA


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