| Codeforces Round 871 (Div. 4) |
|---|
| Закончено |
На ярмарке есть огромная пирамида из консервных банок с $$$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$$$.
Для каждого набора входных данных выведите одно целое число — сумму номеров всех банок, которые упадут.
1091234561014341000000
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$$$.
