## 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:3123Output:1513`

Source limit is 500 bytes. theabd123: 2018-05-29 15:14:03 note there is different formula for even and odd values of N akshat7321: 2018-05-25 13:45:02 Method apart from formula: observe the pattern of the number of triangles facing upward and downward. Store upward and downward triangles in 2 arrays and add them to get the answer. archit4077sh: 2018-05-23 22:25:16 Hey i just derived a recurrence for this f(n) = 3* (f(n-1)-f(n-2)) + f(n-3) + 2 if n is even f(n) = 3* (f(n-1)-f(n-2)) + f(n-3) + 1 if n is odd with base cases f(1)=1 , f(2)=5 ,f(3)=13 Hint: Use principle of inclusion and exclusion... Last edit: 2018-05-23 22:28:19 summer_2: 2018-05-23 19:14:11 explain the solution please? I want to know how that formula comes? Last edit: 2018-05-23 19:15:31 shubham31: 2018-05-11 12:08:29 (n^2) + [ (n(n-1)/2] * [(3+(2*n - 1))/6], shows wrong answer... cross checked it. still no success. n(n+2)(2n+1)/8 works but obviously on calculation for n=3 gives a wrong value. (bad test cases) riyadhrazzaq: 2018-03-24 18:25:35 There's two version of the formula. One uses floor function , another uses odd-even condition. I've used both of them and only got AC for odd-even condition. Can anybody explain that ? kkislay20: 2018-03-10 08:58:48 Use the direct formula...and long long int and you are good to go. bradyawn: 2018-01-24 00:15:38 For those who are wondering why n = 3 is not 9, it is because triangle of not size 1 also count srjsunny: 2018-01-23 14:37:20 use P and C you will get triangles=n(n+2)(2n+1)/8 vikramvarun: 2018-01-12 11:07:58 SPOJ is the worst platform to practice coding. Gives TLE in R for simple operations as well. Do the admins/moderators do any work at all? Can't they see that time limit should be adjusted according to language.