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