Definition

It is said that a sequence of three elements $v = (a_1,a_2,a_3)$ is a Kadomatsu sequence when $v$ satisfies the following conditions.

1. $a_1,a_2,a_3$ are all distinct
2. Among the three elements, $a_2$ is the largest or the smallest

Problem Statement

You are given a sequence $A = (N,N-1,\ldots,2,1,N,N-1,\ldots,2,1)$ of length $2N$.
Output the number of tuples $(i, j, k)$ (where $i < j < k$) such that $(A_i, A_j, A_k)$ is a Kadomatsu sequence.

Input

$T$ test cases are given at once. ($1 \le T \le 10^4$)

$T$
$\text{TestCase}_1$
$\vdots$
$\text{TestCase}_T$

Each test case is given in the following format.

$N$

• $3 \le N \le 10^6$

Output

For each test case, output the answer, separated by newlines.

Sample

7
3
4
5
6
99
501
998244

4
16
40
80
627396
83333000
663158837148037776