For a permutation $$$p$$$ of length $$$n$$$$$$^{\text{∗}}$$$, we define the function:

$$$$$$ f(p) = \sum_{i=1}^{n} \lvert p_i - i \rvert $$$$$$

You are given a number $$$n$$$. You need to compute how many distinct values the function $$$f(p)$$$ can take when considering all possible permutations of the numbers from $$$1$$$ to $$$n$$$.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 500$$$) — the number of numbers in the permutations.

Output

For each test case, output a single integer — the number of distinct values of the function $$$f(p)$$$ for the given length of permutations.

Note

Consider the first two examples of the input.

For $$$n = 2$$$, there are only $$$2$$$ permutations — $$$[1, 2]$$$ and $$$[2, 1]$$$. $$$f([1, 2]) = \lvert 1 - 1 \rvert + \lvert 2 - 2 \rvert = 0$$$, $$$f([2, 1]) = \lvert 2 - 1 \rvert + \lvert 1 - 2 \rvert = 1 + 1 = 2$$$. Thus, the function takes $$$2$$$ distinct values.

For $$$n=3$$$, there are already $$$6$$$ permutations: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[3, 2, 1]$$$, the function values of which will be $$$0, 2, 2, 4, 4$$$, and $$$4$$$ respectively, meaning there are a total of $$$3$$$ values.

Permutation Warm-Up

Examples