F. Inversion Sum
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An Inversion is a pair of indexes $$$(i, j)$$$ such that $$$i \lt j$$$ and $$$a[i] \gt a[j]$$$

Example : [3, 2, 1] has 3 inversions => indexes (1, 2), (1, 3) and (2, 3)

You need to find the sum of inversions of all possible permutations of length n

=> An identity permutation = [1, 2, 3, 4, ..... n]

Input

First line consists of a single integer t, number of testcases [1 <= $$$t$$$ <= $$$10^6$$$]

First line of each test consists of a single integer n, size of permutation [1 <= $$$n$$$ <= $$$10^6$$$]

Output

For each test, print a single integer, the sum of inversions of all possible permutations

Example
Input
4
1
2
3
4
Output
0
1
9
72
Note

For n = 3

[1, 2, 3] = 0 inversions

[1, 3, 2] = 1 inversion

[2, 1, 3] = 1 inversion

[2, 3, 1] = 2 inversions

[3, 1, 2] = 2 inversions

[3, 2, 1] = 3 inversions