The essay

At school, Aziz was asked to write an essay. The deadline is approaching, and Aziz still hasn't written anything. But he knows that his friend Barysh had already completed the same task last year, and Aziz decided to take advantage of it. However, Aziz does not want the plagiarism detection system to be able to detect this. Therefore, Aziz decides to write the words in all sentences of Barysh's composition in reverse order. After that, Aziz calculates the difference between the original proposal and the one that he got.

Barysh's writing consists of $t$ sentences. Each sentence is made up of unique words.

If the number of words in a sentence is denoted by $n$, then the sentence itself can be denoted by sequence $\{1,2,...,n\}$. Then the sentence corresponding to Aziz's composition will be denoted by the sequence $\{n,n-1,...,1\}$.

The difference between the original sentence and Aziz's sentence is calculated as the sum of the absolute values of the differences between the positions where the word occurs in Barysh's sentence and where the same word occurs in Aziz's sentence, for all words in these sentences. For example, in a sentence consisting of $3$ words, if you designate Barysh's sentence as $\{1,2,3\}$, then Aziz's sentence will be $\{3,2,1\}$ and the difference between the sentences will be $|1-3|+|2-2|+|3-1|=4$.

Input

The first line contains one integer $t(1\le t\le 10^5)$ — the number of sentences in Barysh's composition. Each of the following $t$ lines contains one number $n_i(1\le n_i\le 10^9)$ — the number of words in the $i$ - th sentence.

Output

For each sentence, print on a separate line the difference between the sentences of Barysh and Aziz.

Examples