Рассмотрим матрицу размером $$$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$$$).
Для каждого набора входных данных выведите одно целое число — максимальную стоимость среди всех клеток.
512345
19295695
В первом примере есть только $$$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$$$.
