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.


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

hide comments
2015-09-14 22:08:52 Sarthak Munshi
this might help you https://www.youtube.com/watch?v=8be2n67ytqw
2015-08-29 09:12:50 Anakar Parida
Finally did it.. but question was not that good. Though I got the reason for my earlier failure and learnt a lot about Polynomial Differential Theorem
2015-08-24 19:46:20 Anakar Parida
I dont believe am getting WA for direct formula...zzz...
2015-08-19 21:43:11 suhas
500bytes file size limit?seriously? had to compress it like hell. used single alphabets for all variable and function names. :P
2015-08-18 01:32:43
you can do it using recursion , i think tle is caused because of cin,cout use scanf and printf instead
2015-08-05 17:51:00
applied direct formula available on net
2015-07-24 15:49:19
I am plugging the formula to solve the answer, using Long data type in java. but am still getting WA after some test cases. Has anyone faced something similar.
2015-06-20 00:05:10
Answer with the formula (NOT RECURSIVE) is giving TLE... WTF?
2015-06-19 19:25:08 siddharth rai
I am using unsigned long long for everything ...its working on ideone for all cases yet wrong answer..plzz some body help..my code
https://ideone.com/9stMsl
thanx in advance
2015-06-17 16:17:26 Sulabh Kumar
without using formula you'll get TLE whether you use recursion or iteration.don't waste much time...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.