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
narutohokage_1: 2017-01-15 06:59:10

Use long long in C or you will get Wrong Answer and
For N : Number Of Total Triangles (Giving Above 9000, to see if your data type will be able to accommodate)
9000:182300627250
9001:182361395251
9002:182422176755
9003:182482971763
9004:182543780277
9005:182604602298
9006:182665437828
9007:182726286868
9008:182787149420
9009:182848025485

narutohokage_1: 2017-01-15 06:45:57

To all , please do not think that you have tried everything and finally search the internet giving yourself that excuze , i stumbled on this problem , 3 months back and then i tried it for some time , and then it was not a good start , i was not able to do so i left it , i felt it was so tough , and now after 3 months , yesterday i again tried with fresh mind , did not saw any comments , they distract you and made you drift from your original thinking , and i never did any recursion problem , i tried this first i got the method to solve it by recursion , and then looking through that method i got how to get formula , you could derive formula , just be patient.And NEVER GIVE UP , WATCH NARUTO.

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.


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