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
2016-07-22 13:42:54
deriving the formula was fun ...
2016-06-20 16:47:14
what is level 3
2016-05-14 17:27:08
tried a lot to derive the formula!! finally had to check the net :(((
2016-03-11 14:14:08
enjoyed a lot deriving formula ... i will recommend to derive it yourself rather than coping from net, else no point of doing this question
2016-02-07 14:00:39
damn good question.. =D
my 50th
2016-01-21 08:15:40
garmel really good
2015-12-25 07:29:00
There is no diagram of level 3, it makes it difficult to understand what the pattern is.
2015-12-11 20:39:54 Timmy Jose
And at all the people commenting about the formula online, the whole point is to figure out the formula yourself otherwise there's not much point, is there? Heh.
2015-12-11 20:20:26 Timmy Jose
Horribly written question. There should have been some explanation of how the levels are defined instead of randomly providing a pattern for powers of 2.
2015-10-02 01:16:37
hufffffffffff!!!! finally !!!did TONS of silly mistakes.........otherwise qs is easy just need to figure out pattern/formulae
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.