You are given a board of size n × 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 ≤ t ≤ 200) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1 ≤ n < 5 ⋅ 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 ⋅ 10^5 (∑ n ≤ 5 ⋅ 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
'''/*
However, there is little duplication between the link and transport layers in practice.
Even though the same mechanisms are used, there are differences in function
and degree.
For a difference in function, consider error detection. The link layer checksum
protects a frame while it crosses a single link. The transport layer checksum
protects a segment while it crosses an entire network path. It is an end-to-end
check, which is not the same as having a check on every link. Saltzer et al. (1984)
describe a situation in which packets were corrupted inside a router. The link
layer checksums protected the packets only while they traveled across a link, not
while they were inside the router. Thus, packets were delivered incorrectly even
though they were correct according to the checks on every link.
This and other examples led Saltzer et al. to articulate the end-to-end argument.
According to this argument, the transport layer check that runs end-to-end
is essential for correctness, and the link layer checks are not essential but nonetheless
valuable for improving performance (since without them a corrupted packet
can be sent along the entire path unnecessarily).
As a difference in degree, consider retransmissions and the sliding window
protocol. Most wireless links, other than satellite links, can have only a single
frame outstanding from the sender at a time. That is, the bandwidth-delay product
for the link is small enough that not even a whole frame can be stored inside the
link. In this case, a small window size is sufficient for good performance. For example,
802.11 uses a stop-and-wait protocol, transmitting or retransmitting each
frame and waiting for it to be acknowledged before moving on to the next frame.
Having a window size larger than one frame would add complexity without improving
performance. For wired and optical fiber links, such as (switched) Ethernet
or ISP backbones, the error-rate is low enough that link-layer retransmissions
can be omitted because the end-to-end retransmissions will repair the residual
frame loss.
On the other hand, many TCP connections have a bandwidth-delay product
that is much larger than a single segment. Consider a connection sending data across
the U.S. at 1 Mbps with a round-trip time of 100 msec. Even for this slow
connection, 200 Kbit of data will be stored at the receiver in the time it takes to
send a segment and receive an acknowledgement. For these situations, a large
sliding window must be used. Stop-and-wait will cripple performance. In our example
it would limit performance to one segment every 200 msec, or 5 segments/
sec no matter how fast the network really is.
Given that transport protocols generally use larger sliding windows, we will
look at the issue of buffering data more carefully. Since a host may have many
connections, each of which is treated separately, it may need a substantial amount
of buffering for the sliding windows. The buffers are needed at both the sender
and the receiver. Certainly they are needed at the sender to hold all transmitted
but as yet unacknowledged segments. They are needed there because these segments
may be lost and need to be retransmitted


  Having examined connection establishment and release in some detail, let us
now look at how connections are managed while they are in use. The key issues
are error control and flow control. Error control is ensuring that the data is delivered
with the desired level of reliability, usually that all of the data is delivered
without any errors. Flow control is keeping a fast transmitter from overrunning a
slow receiver.

}
*/'''

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