Sum of Shortest Paths in a Diamond Tree

Given T diamond trees. For each diamond tree a positive integer n is provided which represents its number of layers. The diamond tree is constructed as follows:

• The tree has 2n-1 rows. For row r (1 ≤ r ≤ 2n-1), the number of nodes equals r if r ≤ n, and 2n − r if r > n.
• Nodes are identified by their row and column indices: (r, c) where 1 ≤ c ≤ (r if r ≤ n, or 2n − r otherwise).
• Edges are added between nodes in adjacent rows as follows:
  • If r < n (the increasing part), each node (r, c) is connected to (r+1, c) and (r+1, c+1).
  • If r ≥ n (the decreasing part), each node (r, c) is connected to (r+1, c-1) and (r+1, c), if these positions exist.
• The graph is undirected; each edge can be traversed in both directions and has weight 1.

Your task is to compute the sum of the shortest path distances for every unordered pair of nodes in the diamond tree.

Note: For a diamond tree with only 1 layer, the tree consists of a single node and the answer is 0.

inputFormat

The first line contains a single integer T denoting the number of test cases.
For each test case, there is one line containing an integer n (n ≥ 1), the number of layers of the diamond tree.

outputFormat

For each test case, output a single line with one integer – the sum of the shortest path distances for all pairs of nodes in the diamond tree.

sample

3
1
2
3

0
4