A. Максимальное соседство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим матрицу размером $$$n \times n$$$, заполненную числами следующим образом:

  • первая строка содержит целые числа от $$$1$$$ до $$$n$$$ слева направо;
  • вторая строка содержит целые числа от $$$(n+1)$$$ до $$$2n$$$ слева направо;
  • этот шаблон продолжается до $$$n$$$-й строки, которая содержит целые числа от $$$(n^2-n+1)$$$ до $$$n^2$$$ слева направо.

Определим стоимость клетки следующим образом: значение, записанное в ней, плюс сумма значений в соседних клетках. Две клетки считаются соседними, если у них общая сторона.

Ваша задача — вычислить максимальную стоимость среди всех клеток.

Матрица для $$$n = 4$$$ и оптимальный ответ для нее. У желтой клетки максимальная стоимость; зеленые клетки — ее соседи. Стоимость клетки равна $$$15+11+14+16=56$$$.
Входные данные

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

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

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

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

Пример
Входные данные
5
1
2
3
4
5
Выходные данные
1
9
29
56
95
Примечание

В первом примере есть только $$$1$$$ клетка со стоимостью $$$1$$$.

Во втором примере клетка со значением $$$4$$$ имеет максимальную стоимость: $$$4 + 2 + 3 = 9$$$.

В третьем примере клетка со значением $$$8$$$ имеет максимальную стоимость: $$$8 + 5 + 7 + 9 = 29$$$.

В четвертом примере клетка со значением $$$15$$$ имеет максимальную стоимость: $$$15 + 11 + 14 + 16 = 56$$$.

В пятом примере клетка со значением $$$19$$$ имеет максимальную стоимость: $$$19 + 14 + 18 + 20 + 24 = 95$$$.