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

На ярмарке есть огромная пирамида из консервных банок с $$$2023$$$ рядами, пронумерованными в стандартном порядке, как показано на рисунке.

Если вначале попасть в банку с номером $$$9^2$$$, то упадут все банки, покрашенные в красный цвет на рисунке выше.

Вы бросаете мяч в пирамиду, и он попадает в одну банку с номером $$$n^2$$$. Это приводит к тому, что все банки, которые находятся над этой банкой, падают (то есть банка $$$n^2$$$ падает, затем падают банки, непосредственно находящиеся над $$$n^2$$$, затем банки, непосредственно находящиеся над этими банками, и так далее). Например, на рисунке выше показаны банки, которые упадут, если попасть в банку $$$9^2$$$.

Какова сумма номеров всех банок, которые упадут? Напомним, что $$$n^2 = n \times n$$$.

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

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

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — это означает, что банка, в которую вы попали, имеет номер $$$n^2$$$.

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

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

Пример
Входные данные
10
9
1
2
3
4
5
6
10
1434
1000000
Выходные данные
156
1
5
10
21
39
46
146
63145186
58116199242129511
Примечание

Первый набор входных данных изображен в условии. Сумма номеров, которые упадут, равна $$$$$$1^2 + 2^2 + 3^2 + 5^2 + 6^2 + 9^2 = 1 + 4 + 9 + 25 + 36 + 81 = 156.$$$$$$

Во втором наборе входных данных упадет только банка с номером $$$1^2$$$, поэтому ответ равен $$$1^2=1$$$.

В третьем наборе входных данных упадут банки с номерами $$$1^2$$$ и $$$2^2$$$, поэтому ответ равен $$$1^2+2^2=1+4=5$$$.

В четвертом наборе входных данных упадут банки с номерами $$$1^2$$$ и $$$3^2$$$, поэтому ответ равен $$$1^2+3^2=1+9=10$$$.

В пятом наборе входных данных упадут банки с номерами $$$1^2$$$, $$$2^2$$$ и $$$4^2$$$, поэтому ответ равен $$$1^2+2^2+4^2=1+4+16=21$$$.