C. Ещё одна задача про перестановки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андрей только начинает придумывать задачи, и это ему тяжело даётся. Поэтому он придумал странную задачу про перестановки$$$^{\dagger}$$$, и просит её решить. Получится ли у вас это сделать?

Назовем стоимостью перестановки $$$p$$$ длины $$$n$$$ значение выражения:

$$$(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$$$.

Найдите максимальную стоимость среди всех перестановок длины $$$n$$$.

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

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

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

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 250$$$) — длину перестановки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$500$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальную стоимость среди всех перестановок длины $$$n$$$.

Пример
Входные данные
5
2
4
3
10
20
Выходные данные
2
17
7
303
2529
Примечание

В первом наборе входных данных перестановкой с максимальной стоимостью является $$$[2, 1]$$$. Стоимость равна $$$2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2$$$.

Во втором наборе входных данных перестановкой с максимальной стоимостью является $$$[1, 2, 4, 3]$$$. Стоимость равна $$$1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$$$.