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

Вам задана доска размера $$$n \times n$$$, где $$$n$$$ нечетно (не кратно $$$2$$$). Изначально в каждой клетке доски расположена одна фигура.

За один ход вы можете выбрать ровно одну фигуру, расположенную в какой-либо клетке и передвинуть ее в одну из клеток, имеющую общую сторону или угол с текущей клеткой, то есть из клетки $$$(i, j)$$$ вы можете передвинуть фигуру в клетку:

  • $$$(i - 1, j - 1)$$$;
  • $$$(i - 1, j)$$$;
  • $$$(i - 1, j + 1)$$$;
  • $$$(i, j - 1)$$$;
  • $$$(i, j + 1)$$$;
  • $$$(i + 1, j - 1)$$$;
  • $$$(i + 1, j)$$$;
  • $$$(i + 1, j + 1)$$$;

Конечно же, вы не можете двигать фигуры в клетки за пределами доски. Допустимо, что после хода в одной клетке будет находиться несколько фигур.

Ваша задача — найти минимальное количество ходов, необходимое, чтобы собрать все фигуры в одной клетке (т.е. в $$$n^2-1$$$ клетках должно быть расположено $$$0$$$ фигур и в одной клетке должны быть расположены $$$n^2$$$ фигур).

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 200$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Единственная строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n < 5 \cdot 10^5$$$) — размер доски. Гарантируется, что $$$n$$$ нечетно (не делится на $$$2$$$).

Также гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$5 \cdot 10^5$$$ ($$$\sum n \le 5 \cdot 10^5$$$).

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

Для каждого набора тестовых данных выведите ответ — минимальное количество ходов, необходимое, чтобы собрать все фигуры в одной клетке.

Пример
Входные данные
3
1
5
499993
Выходные данные
0
40
41664916690999888