You are given a board of size $n \times n$, where $n$ is odd (not divisible by $2$). Initially, each cell of the board contains one figure.

In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell $(i, j)$ you can move the figure to cells:   $(i - 1, j - 1)$;  $(i - 1, j)$;  $(i - 1, j + 1)$;  $(i, j - 1)$;  $(i, j + 1)$;  $(i + 1, j - 1)$;  $(i + 1, j)$;  $(i + 1, j + 1)$; 

Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell.

Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. $n^2-1$ cells should contain $0$ figures and one cell should contain $n^2$ figures).

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 200$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($1 \le n < 5 \cdot 10^5$) — the size of the board. It is guaranteed that $n$ is odd (not divisible by $2$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$ ($\sum n \le 5 \cdot 10^5$).


-----Output-----

For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.


-----Example-----
Input
3
1
5
499993

Output
0
40
41664916690999888

Difficulty: introductory

Starter code:

Solutions:
a=int(input())

for ufui in range(a):
    val=int(input())

    num=val//2 + 1
    count=0

    for i in range(num):
        count=count+i*((2*i+1)**2 - (2*i-1)**2)

    print (count)
    


import sys
input = sys.stdin.readline
rInt = lambda: int(input())
mInt = lambda: list(map(int, input().split()))
rLis = lambda: list(map(int, input().split()))

t = rInt()
for _ in range(t):
    n = rInt()
    center = n//2
    out = 0
    for i in range(1, n // 2 + 1):
        out += i * i * 8
    print(out)


import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n = ni()
    c = 0
    for i in range(n//2):
        c += (i+1)*(i+1)*2*4
    print(c)
    return

# solve()

T = ni()
for _ in range(T):
    solve()



t = int(input())

for loop in range(t):

    n = int(input())

    ans = 0
    for i in range(n//2+1):
        ans += i * ( (i*2+1)**2 - (i*2-1)**2 )

    print (ans)


for _ in range(int(input())):
    n=int(input())
    x=n//2
    res=0
    for i in range(1,x+1):
        res+=8*i*i
    print(res)


from sys import stdin, stdout, setrecursionlimit
for _ in range(int(input())):
    n = int(input())
    summa = 0
    while n > 0:
        summa += 4 * (n // 2) + 4 * (n - 2) * (n // 2)
        n -= 2
    print(summa)








t = int(input())
for i in range(t):
    n = int(input())
    s = 0
    for j in range(1, (n + 1) // 2):
        s += j * ((2*j + 1) * 4 - 4)
    print(s)



def solve():
    n = int(input())
    iters = n // 2
    out = 0
    for i in range(iters + 1):
        out += 8 * i * i
    print(out)

def __starting_point():
    t = int(input())
    for tc in range(t):
        solve()
__starting_point()

for _ in range(int(input())):
    n = int(input())
    print(sum(i * ((2 * i + 1) ** 2 - (2 * (i - 1) + 1) ** 2) for i in range(1, n // 2 + 1)))


import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
t=1
t=int(input())
for _ in range(t):
    n=int(input())
    ans=0
    for i in range(1,(n+1)//2):
        ans+=i*8*i 
    print(ans)


import sys
input = sys.stdin.readline
from itertools import accumulate
S=[i*4*(2*i) for i in range(5*10**5+2)]
ANS=list(accumulate(S))

t=int(input())
for tests in range(t):
    n=int(input())
    print(ANS[n//2])


def getN():
    return int(input())
def getNM():
    return list(map(int, input().split()))
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353

def solve():
    n = getN()
    ans = 0
    radius = n // 2
    for r in range(radius):
        ra = r + 1
        ans += ra *((ra * 2 + 1) ** 2 - (ra * 2 - 1) ** 2)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
def __starting_point():
    main()


__starting_point()

q = int(input())
for _ in range(q):
	n = int(input())
	k = n//2
	su = k*(k+1)//2
	su += (2*k*(k*(k+1)//2))
	su *= 4
	print(su*2//3)


for f in range(int(input())):
    n=int(input())
    m=n//2
    prev=1
    cur=3
    mov=0
    for i in range(m):
        mov+=(i+1)*(cur**2-prev**2)
        prev+=2
        cur+=2
    print(mov)

import math 
def ri():
    return map(int,input().split())
def li():
    return list(map(int,input().split()))
def inp():
    return int(input())
def si():
    return input()
def pYes():
    print("YES")
def pNo():
    print("NO")
def plist(l):
    print("".join(l))
t = int(input())
for i in range(t):
    n = int(input())
    ans=0
    t=1
    for k in range(3,n+1,2):
        
        ans+=(2*k + (k-2)*2)*t
        t=t+1
    print(ans)

from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n = ri()
    answer = 0
    half = (n + 1) // 2
    for i in range(1, half):
        ring = (2 * i + 1)**2 - (2 * i - 1)**2
        answer += i * ring
    print (answer)





mode = 'T'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


t=int(input())
for _ in range(t):
    n=int(input())
    s=0
    for i in range(n//2):
        s=s+8*(i+1)*(i+1)
    print(s)

N = 5*(10**5)+1
dp = [0 for i in range(N)]
dp[1] = 0
for i in range(3,N,2):
	dp[i] = dp[i-2]+8*(i//2)*(i//2)
t = int(input())
for y in range(t):
	n = int(input())
	print(dp[n])
	


# encoding: utf-8
import sys
sys.setrecursionlimit(10**6)


def __starting_point():
    # sys.stdin = open('1.std.in', 'r')
    nofkase = int(input())
    for kase in range(nofkase):
        n = int(input())
        n = n // 2
        print(n*(n+1)*(n+n+1)*8//6)

__starting_point()

t=int(input())
for i in range(t):
    n=int(input())
    ans=(n//2)*n**2
    for j in range(n//2):
        ans-=(2*j+1)**2
    print(ans)

t=int(input())
for _ in range(t):
	n=int(input())
	ans=0
	for i in range(1,n//2+1):
		ans+=8*i*i
	print(ans)

def solve(k):
    res = 0
    for i in range((k+1)//2):
        res += 4*2*i**2
    return res

strr = input()
for _ in range(int(strr)):
    k = int(input())
    print(solve(k))


import sys
import os
import time
import collections
from collections import Counter, deque
import itertools
import math
import timeit
import random
import string

#########################
# imgur.com/Pkt7iIf.png #
#########################

def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r

def divs(n, start=1):
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors

def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t

def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end)
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)

########################################################################################################################
# input = sys.stdin.readline

for _ in range(ii()):
    n = ii()
    res = 0
    cs = 8
    for i in range(1, n//2 + 1):
        res += cs * i
        cs += 8
    print(res)



t = int(input())
while t:
    n = int(input())
    ans = 0
    if n==1: print(0)
    else:
        for i in range(1, n//2 + 1):
            ans += 8*i*i
        print(ans)
    t -= 1

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        ans = 0
        for i in range(1,n + 1,2):
            ans += (4 * i - 4) * (i // 2)
        print(ans)
    return

def __starting_point():
    main()
__starting_point()

import sys
input=sys.stdin.readline
from collections import defaultdict as dd
t=int(input())
while t:
    n=int(input())
    a=8
    res=0
    for i in range(1,n//2+1):
        res+=a*i*i
    print(res)
    t-=1

for _ in range(int(input())):
    n = int(input())
    c = n // 2, n // 2

    s = 0

    for j in range(n):
        s += max(abs(c[0] - 0), abs(c[1] - j))

    ts = s

    for i in range(1, n // 2 + 1):
        s -= n - 2 * i
        ts += s

    print(ts * 2 - s)

T = int(input())

for t in range(T):
    N = int(input())

    answer = 0
    i = 0
    moves = 0
    nb = 0
    while i < N//2:
        i += 1
        nb += 8
        answer += nb * i
    print(answer)


from sys import stdin

def func(n):
    if n == 1:
        return 0
    x = n//2
    m = 0
    while(x > 0):
        m += 4*(n -1)*x
        x -= 1
        n -= 2
    return m

for _ in range(int(input())):
    n = int(input())
    #l = list(map(int, stdin.readline().split()))
    #n, k = map(int, input().split())
    print(func(n))