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
love1024: 2017-06-15 11:53:28

Lots of formulas of triangular number to derive.

Last edit: 2017-06-15 11:53:44
rishabhm123: 2017-05-30 00:05:57

All test cases are getting right..
As mentioned above by @narutohokage_1 in orders of 9000.
Still getting WA

noxiousav: 2017-05-23 14:39:53

Source Code limit not fit for java!

sushanth_r: 2017-04-11 18:16:10

Did it the way it should be done i.e by figuring out a pattern after working for 2 hours. Result? TLE.
Applied the formula and AC with 0.0
All that work in vain
Smh.

shauryauppal: 2017-03-10 20:18:50

formula use->(n*(n+2)*(2n+1))/8

cake_is_a_lie: 2017-02-10 17:16:27

I got the recursive formula for this one, then 3 WAs because I pre-computed it up to 999999 instead of 1000000 :-) careful with your < vs <=.

nilabja16180: 2017-02-10 15:25:38

Used Direct formula!

rohit9934: 2017-02-09 06:52:11

For Level 5,what is the answer? 49?

sonudoo: 2017-02-07 14:21:57

4 hours of pen paper. 13 pages of mathematics. One simple condensed formula. Green light..

narutohokage_1: 2017-01-15 07:01:04

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 ,


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