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
Govind Lahoti: 2015-02-08 14:12:17

nice problem :)
Formula derivation is fun.

Abhishek pratap singh: 2014-12-09 13:16:19

@ayushi for the 4 the level
there are 27 triangles ( 20 normal triangles and 7 inverted triangles (i think you are missing the big inverted triangle)) :)
and if you are getting WA on the 9th test case then try changing all the int(s) to long long unsigned int(s)

Last edit: 2014-12-09 13:16:42
ayushi agarwal: 2014-11-06 19:23:09

how the answer for level 4 is 27?? Mine is coming 26??

Tizen: 2014-06-30 14:48:17

@Priyam Mitra - For Level 3, there will be 9 small triangles, 3 medium triangles and 1 big triangle.

candide: 2014-05-25 00:11:52

By omitting the figure for the stage 3, problem statement is confusing and suggests that at each step, every triangle is divided into four triangles. As comments show, many spojer are confused, and some even believe that 13 is an erroneous response for the stage 3... So, to clarify : at stage N, the sides of the initial triangle are divided into N parts. And, indeed, 13 is the correct counting at stage 3.

Last edit: 2014-05-25 01:35:02

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