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
sudeep_11: 2017-01-14 20:10:25

easy problem if you find out formula

cobra_laden: 2017-01-06 12:48:28

long gave me 2 WAs ---___---

kg93999: 2017-01-05 19:39:41

hint:- https://www.youtube.com/watch?v=8be2n67ytqw

shreyanshgeek: 2016-12-27 15:01:16

A little knowledge about the concept of special series sum will let u do it easily!!

spartax: 2016-12-01 06:09:07

Good Problem

tjain1999: 2016-11-28 13:42:00

@Ashok Thanks you saved me. I was pretty annoyed so as to why I was getting the wrong answer. Btw I will check the limits in the future.

pedro: 2016-10-26 19:54:01

really liked the deriving part of formula...

jjchai: 2016-10-08 20:18:59

Beware of the type of variables you use. You are calculating something very big. If overflow happens you get wrong answer.

Ashok: 2016-09-16 14:40:59

Java users use long,6 WA :( for that

black_jack1: 2016-09-15 21:56:10

Source Code limit is too low. Not fit for java!!


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