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
coolboy19521: 2024-05-22 16:49:35

How does level 3 look like? Does it have 2^3 small triangles? It could have been better if it was shown in problem statement.

fritzp: 2024-03-12 05:29:54

IwillapplyfortheInternationalObfuscatedCCodeContestwithmycode

the_art_maniac: 2021-06-10 16:42:46

Don't watch video explanations.
Derive the formula on your own...
*HINT*:- Its Arithmetic progression with variable difference , grab your pen and notebook :)

akshat_19: 2021-05-09 14:31:55

Use unsigned long long and take your time to get "correct" formula.

ayush_06: 2021-02-05 18:42:41

Giving wrong answer after test case 8??

avi_9314: 2020-10-10 19:37:48

solution should be less than 500 b .. gareebi level : SPOJ

kapilsukrit2: 2020-09-23 13:42:47

TAKE INPUT AS LONG LONG UNSIGNED!!!! VV IMP

manxmaniac: 2020-08-23 13:51:32

@aryan_0406 you got this i believe in you dude

blackhat_130: 2020-03-27 22:19:48

use long long also during accepting input than only in writing answer otherwise you'll get wrong answer.
This error costs me 3 wrong submission.

Last edit: 2020-03-27 22:21:13
aryan__0406: 2020-03-20 19:55:10

Nothing is impossible friends,use your mind and solve this problem. I am also trying this problem from the previous one year and i am confident that one day i will be able to solve this problem efficiently.


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