A. Перестановочный прогрев
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для перестановки $$$p$$$ длины $$$n$$$$$$^{\text{∗}}$$$ определим функцию:

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

Вам задано число $$$n$$$. Нужно вычислить, сколько различных значений может принимать функция $$$f(p)$$$, если рассмотреть все возможные перестановки чисел от $$$1$$$ до $$$n$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 500$$$) — количество чисел в перестановках.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных значений функции $$$f(p)$$$ для заданной длины перестановок.

Пример
Входные данные
5
2
3
8
15
43
Выходные данные
2
3
17
57
463
Примечание

Рассмотрим два первых примера входных данных.

Для $$$n = 2$$$ существует всего $$$2$$$ перестановки — $$$[1, 2]$$$ и $$$[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$$$. Значит, функция принимает $$$2$$$ различных значения.

Для $$$n=3$$$ существует уже $$$6$$$ перестановок: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[3, 2, 1]$$$, значения функции от которых будут равны $$$0, 2, 2, 4, 4$$$ и $$$4$$$ соответственно, то есть всего $$$3$$$ значения.