e-olymp
Competitions

2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8

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 proposal 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 sequence {n, n - 1,..., 1}.

The difference between the original sentence and Aziz's sentence is considered as the sum of 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 of 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 |13| + |22| + |31| = 4.

Input

The first line contains one integer t - the number of sentences in Barysh's composition. Each of the following t lines contains one number ni - 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.

Restrictions

  • 1t105
  • 1ni109

Subtasks

This problem consists of 2 subtasks:

SubtasksRestrictionsPoints
0Example0 points
1t100, ni10427 points
2No additional restrictions73 points
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
4
3
7
Output example #1
8
4
24
Source 2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8