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
Pradd: 2015-06-16 14:32:17

Use long long in place of int in C . Long Long = AC, Int = WA

Gaurav Jain: 2015-06-15 14:16:39

My solution http://ideone.com/XC1fwx is showing runtime error. Can anyone help me to detect it?

r0bo_dart: 2015-06-12 20:10:57

lame question... formula oriented.. using recursion fails for N > 10^5
Then I thought that maybe there are too many recursion calls. I implemented using while loop. That gives a TLE.
Finally just plugged in the formula and it accepted it. phew. waste of an hour.

Rishabh Joshi: 2015-05-30 14:02:21

using pow() caused WA.

Babloo: 2015-05-28 08:46:21

http://www.transum.org/Software/SW/Starter_of_the_day/starter_September23.asp may be useful

kobe24: 2015-05-27 00:26:59

http://jwilson.coe.uga.edu/emt725/Bob/Count.Triangles.II.html
this properly shows the idea

Anton Chigurh: 2015-05-23 20:33:42

Because of the source code limitation, I literally had to minify my Java code the same way JavaScript files are minified.

scyth3r: 2015-05-07 00:18:45

"telescoping series" made calculations easy......

Phong: 2015-04-21 15:45:07

@Singh - Thank you I got it :D

hareesh: 2015-04-21 08:47:37

Test Cases (Use them to get the pattern)
1 : 1
2 : 5
3 : 13
4 : 27
5 : 48
6 : 78
7 : 118
8 : 170
9 : 235
10 : 315


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