## 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
 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 Dushyant Singh: 2015-04-18 22:10:48 @Phong - We add layers of triangles level by level. In level 1, we have 1 triangle. In level 2, we add second layer of triangles below first layer such that a big triangle is formed. Same thing is for other levels. So for level 3, we add third layer of triangles below second level. Phong: 2015-04-18 16:21:46 I don't see why stage 4 is like that. How about stage 3? How could it be drawed ? Confused @@ Prasanna Patil: 2015-04-17 16:55:07 After learning a lot math about triangles. It became so easy. Just 3 lines code in python. shantanu tripathi: 2015-04-16 11:39:34 use unsigned long long to count the no of triangles.... KATURI SAI KIRAN: 2015-04-03 13:25:48 Thanks @candide for your explaination. You are correct. Even I was confused with the question Aditya: 2015-03-29 08:24:48 Thanks Abhishek for suggestion of long long unsigned int.... I got 2 WA for this mistake. kbt: 2015-03-18 12:53:02 nice problem. formula derievation takes time nd after that its a 10 line code. #cakewalk Malfple: 2015-02-19 15:40:39 ah 3.1M ... 3.2M ... mine is 48M. Not using a single formula because i don't know any :P

 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