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
[{"code": "a=int(input())\n\nfor ufui in range(a):\n    val=int(input())\n\n    num=val//2 + 1\n    count=0\n\n    for i in range(num):\n        count=count+i*((2*i+1)**2 - (2*i-1)**2)\n\n    print (count)\n    \n", "passed": true, "time": 0.8, "memory": 14160.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\nrInt = lambda: int(input())\nmInt = lambda: list(map(int, input().split()))\nrLis = lambda: list(map(int, input().split()))\n\nt = rInt()\nfor _ in range(t):\n    n = rInt()\n    center = n//2\n    out = 0\n    for i in range(1, n // 2 + 1):\n        out += i * i * 8\n    print(out)\n", "passed": true, "time": 0.23, "memory": 14208.0, "status": "done"}, {"code": "import sys\n\nreadline = sys.stdin.readline\nreadall = sys.stdin.read\nns = lambda: readline().rstrip()\nni = lambda: int(readline().rstrip())\nnm = lambda: map(int, readline().split())\nnl = lambda: list(map(int, readline().split()))\nprn = lambda x: print(*x, sep='\\n')\n\n\ndef solve():\n    n = ni()\n    c = 0\n    for i in range(n//2):\n        c += (i+1)*(i+1)*2*4\n    print(c)\n    return\n\n# solve()\n\nT = ni()\nfor _ in range(T):\n    solve()\n", "passed": true, "time": 0.35, "memory": 14372.0, "status": "done"}, {"code": "\nt = int(input())\n\nfor loop in range(t):\n\n    n = int(input())\n\n    ans = 0\n    for i in range(n//2+1):\n        ans += i * ( (i*2+1)**2 - (i*2-1)**2 )\n\n    print (ans)\n", "passed": true, "time": 0.76, "memory": 14348.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n=int(input())\n    x=n//2\n    res=0\n    for i in range(1,x+1):\n        res+=8*i*i\n    print(res)\n", "passed": true, "time": 0.22, "memory": 14252.0, "status": "done"}, {"code": "from sys import stdin, stdout, setrecursionlimit\nfor _ in range(int(input())):\n    n = int(input())\n    summa = 0\n    while n > 0:\n        summa += 4 * (n // 2) + 4 * (n - 2) * (n // 2)\n        n -= 2\n    print(summa)\n\n\n\n\n\n\n", "passed": true, "time": 0.33, "memory": 14200.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n    n = int(input())\n    s = 0\n    for j in range(1, (n + 1) // 2):\n        s += j * ((2*j + 1) * 4 - 4)\n    print(s)", "passed": true, "time": 0.73, "memory": 14164.0, "status": "done"}, {"code": "\n\ndef solve():\n    n = int(input())\n    iters = n // 2\n    out = 0\n    for i in range(iters + 1):\n        out += 8 * i * i\n    print(out)\n\ndef __starting_point():\n    t = int(input())\n    for tc in range(t):\n        solve()\n__starting_point()", "passed": true, "time": 0.23, "memory": 14136.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    print(sum(i * ((2 * i + 1) ** 2 - (2 * (i - 1) + 1) ** 2) for i in range(1, n // 2 + 1)))\n", "passed": true, "time": 0.76, "memory": 14368.0, "status": "done"}, {"code": "import math\nimport time\nfrom collections import defaultdict,deque\nfrom sys import stdin,stdout\nfrom bisect import bisect_left,bisect_right\nt=1\nt=int(input())\nfor _ in range(t):\n    n=int(input())\n    ans=0\n    for i in range(1,(n+1)//2):\n        ans+=i*8*i \n    print(ans)\n", "passed": true, "time": 0.25, "memory": 14240.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\nfrom itertools import accumulate\nS=[i*4*(2*i) for i in range(5*10**5+2)]\nANS=list(accumulate(S))\n\nt=int(input())\nfor tests in range(t):\n    n=int(input())\n    print(ANS[n//2])\n", "passed": true, "time": 0.89, "memory": 61540.0, "status": "done"}, {"code": "def getN():\n    return int(input())\ndef getNM():\n    return list(map(int, input().split()))\ndef getList():\n    return list(map(int, input().split()))\n\nfrom collections import defaultdict, deque\nimport math\nimport copy\nfrom bisect import bisect_left\n\nimport sys\n# sys.setrecursionlimit(1000000)\nINF = 10 ** 17\nMOD = 998244353\n\ndef solve():\n    n = getN()\n    ans = 0\n    radius = n // 2\n    for r in range(radius):\n        ra = r + 1\n        ans += ra *((ra * 2 + 1) ** 2 - (ra * 2 - 1) ** 2)\n    print(ans)\n\ndef main():\n    n = getN()\n    for _ in range(n):\n        solve()\ndef __starting_point():\n    main()\n\n\n__starting_point()", "passed": true, "time": 0.83, "memory": 14364.0, "status": "done"}, {"code": "q = int(input())\nfor _ in range(q):\n\tn = int(input())\n\tk = n//2\n\tsu = k*(k+1)//2\n\tsu += (2*k*(k*(k+1)//2))\n\tsu *= 4\n\tprint(su*2//3)\n", "passed": true, "time": 0.22, "memory": 14240.0, "status": "done"}, {"code": "for f in range(int(input())):\n    n=int(input())\n    m=n//2\n    prev=1\n    cur=3\n    mov=0\n    for i in range(m):\n        mov+=(i+1)*(cur**2-prev**2)\n        prev+=2\n        cur+=2\n    print(mov)", "passed": true, "time": 0.87, "memory": 14232.0, "status": "done"}, {"code": "import math \ndef ri():\n    return map(int,input().split())\ndef li():\n    return list(map(int,input().split()))\ndef inp():\n    return int(input())\ndef si():\n    return input()\ndef pYes():\n    print(\"YES\")\ndef pNo():\n    print(\"NO\")\ndef plist(l):\n    print(\"\".join(l))\nt = int(input())\nfor i in range(t):\n    n = int(input())\n    ans=0\n    t=1\n    for k in range(3,n+1,2):\n        \n        ans+=(2*k + (k-2)*2)*t\n        t=t+1\n    print(ans)", "passed": true, "time": 0.28, "memory": 14248.0, "status": "done"}, {"code": "from collections import defaultdict as dd\nfrom collections import deque\nimport bisect\nimport heapq\n\ndef ri():\n    return int(input())\n\ndef rl():\n    return list(map(int, input().split()))\n\n\ndef solve():\n    n = ri()\n    answer = 0\n    half = (n + 1) // 2\n    for i in range(1, half):\n        ring = (2 * i + 1)**2 - (2 * i - 1)**2\n        answer += i * ring\n    print (answer)\n\n\n\n\n\nmode = 'T'\n\nif mode == 'T':\n    t = ri()\n    for i in range(t):\n        solve()\nelse:\n    solve()\n", "passed": true, "time": 0.81, "memory": 14128.0, "status": "done"}, {"code": "t=int(input())\nfor _ in range(t):\n    n=int(input())\n    s=0\n    for i in range(n//2):\n        s=s+8*(i+1)*(i+1)\n    print(s)", "passed": true, "time": 0.24, "memory": 14112.0, "status": "done"}, {"code": "N = 5*(10**5)+1\ndp = [0 for i in range(N)]\ndp[1] = 0\nfor i in range(3,N,2):\n\tdp[i] = dp[i-2]+8*(i//2)*(i//2)\nt = int(input())\nfor y in range(t):\n\tn = int(input())\n\tprint(dp[n])\n\t\n", "passed": true, "time": 0.52, "memory": 29012.0, "status": "done"}, {"code": "# encoding: utf-8\nimport sys\nsys.setrecursionlimit(10**6)\n\n\ndef __starting_point():\n    # sys.stdin = open('1.std.in', 'r')\n    nofkase = int(input())\n    for kase in range(nofkase):\n        n = int(input())\n        n = n // 2\n        print(n*(n+1)*(n+n+1)*8//6)\n\n__starting_point()", "passed": true, "time": 0.23, "memory": 14144.0, "status": "done"}, {"code": "t=int(input())\nfor i in range(t):\n    n=int(input())\n    ans=(n//2)*n**2\n    for j in range(n//2):\n        ans-=(2*j+1)**2\n    print(ans)", "passed": true, "time": 0.44, "memory": 14328.0, "status": "done"}, {"code": "t=int(input())\nfor _ in range(t):\n\tn=int(input())\n\tans=0\n\tfor i in range(1,n//2+1):\n\t\tans+=8*i*i\n\tprint(ans)", "passed": true, "time": 0.21, "memory": 14308.0, "status": "done"}, {"code": "def solve(k):\n    res = 0\n    for i in range((k+1)//2):\n        res += 4*2*i**2\n    return res\n\nstrr = input()\nfor _ in range(int(strr)):\n    k = int(input())\n    print(solve(k))\n", "passed": true, "time": 0.42, "memory": 14252.0, "status": "done"}, {"code": "import sys\nimport os\nimport time\nimport collections\nfrom collections import Counter, deque\nimport itertools\nimport math\nimport timeit\nimport random\nimport string\n\n#########################\n# imgur.com/Pkt7iIf.png #\n#########################\n\ndef sieve(n):\n    if n < 2: return list()\n    prime = [True for _ in range(n + 1)]\n    p = 3\n    while p * p <= n:\n        if prime[p]:\n            for i in range(p * 2, n + 1, p):\n                prime[i] = False\n        p += 2\n    r = [2]\n    for p in range(3, n + 1, 2):\n        if prime[p]:\n            r.append(p)\n    return r\n\ndef divs(n, start=1):\n    divisors = []\n    for i in range(start, int(math.sqrt(n) + 1)):\n        if n % i == 0:\n            if n / i == i:\n                divisors.append(i)\n            else:\n                divisors.extend([i, n // i])\n    return divisors\n\ndef divn(n, primes):\n    divs_number = 1\n    for i in primes:\n        if n == 1:\n            return divs_number\n        t = 1\n        while n % i == 0:\n            t += 1\n            n //= i\n        divs_number *= t\n\ndef flin(d, x, default=-1):\n    left = right = -1\n    for i in range(len(d)):\n        if d[i] == x:\n            if left == -1: left = i\n            right = i\n    if left == -1:\n        return default, default\n    else:\n        return left, right\n\ndef ceil(n, k): return n // k + (n % k != 0)\ndef ii(): return int(input())\ndef mi(): return map(int, input().split())\ndef li(): return list(map(int, input().split()))\ndef lcm(a, b): return abs(a * b) // math.gcd(a, b)\ndef prr(a, sep=' ', end='\\n'): print(sep.join(map(str, a)), end=end)\ndef dd(): return collections.defaultdict(int)\ndef ddl(): return collections.defaultdict(list)\n\n########################################################################################################################\n# input = sys.stdin.readline\n\nfor _ in range(ii()):\n    n = ii()\n    res = 0\n    cs = 8\n    for i in range(1, n//2 + 1):\n        res += cs * i\n        cs += 8\n    print(res)\n\n", "passed": true, "time": 0.22, "memory": 14300.0, "status": "done"}, {"code": "t = int(input())\nwhile t:\n    n = int(input())\n    ans = 0\n    if n==1: print(0)\n    else:\n        for i in range(1, n//2 + 1):\n            ans += 8*i*i\n        print(ans)\n    t -= 1", "passed": true, "time": 0.21, "memory": 14228.0, "status": "done"}, {"code": "#  =========     /\\       /|    |====/|\n#      |        /  \\       |    |   / |\n#      |       /____\\      |    |  /  |\n#      |      /      \\     |    | /   |\n#  ========= /        \\  =====  |/====|  \n#  code\n\ndef main():\n    t = int(input())\n    for _ in range(t):\n        n = int(input())\n        ans = 0\n        for i in range(1,n + 1,2):\n            ans += (4 * i - 4) * (i // 2)\n        print(ans)\n    return\n\ndef __starting_point():\n    main()\n__starting_point()", "passed": true, "time": 0.25, "memory": 14184.0, "status": "done"}, {"code": "import sys\ninput=sys.stdin.readline\nfrom collections import defaultdict as dd\nt=int(input())\nwhile t:\n    n=int(input())\n    a=8\n    res=0\n    for i in range(1,n//2+1):\n        res+=a*i*i\n    print(res)\n    t-=1", "passed": true, "time": 0.21, "memory": 14348.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    c = n // 2, n // 2\n\n    s = 0\n\n    for j in range(n):\n        s += max(abs(c[0] - 0), abs(c[1] - j))\n\n    ts = s\n\n    for i in range(1, n // 2 + 1):\n        s -= n - 2 * i\n        ts += s\n\n    print(ts * 2 - s)", "passed": true, "time": 0.7, "memory": 14124.0, "status": "done"}, {"code": "T = int(input())\n\nfor t in range(T):\n    N = int(input())\n\n    answer = 0\n    i = 0\n    moves = 0\n    nb = 0\n    while i < N//2:\n        i += 1\n        nb += 8\n        answer += nb * i\n    print(answer)\n", "passed": true, "time": 0.24, "memory": 14320.0, "status": "done"}, {"code": "from sys import stdin\n\ndef func(n):\n    if n == 1:\n        return 0\n    x = n//2\n    m = 0\n    while(x > 0):\n        m += 4*(n -1)*x\n        x -= 1\n        n -= 2\n    return m\n\nfor _ in range(int(input())):\n    n = int(input())\n    #l = list(map(int, stdin.readline().split()))\n    #n, k = map(int, input().split())\n    print(func(n))\n", "passed": true, "time": 0.25, "memory": 14256.0, "status": "done"}]