Для квадратной матрицы целых чисел размера $$$n \times n$$$ определим ее красоту следующим образом: для каждой пары соседних по стороне элементов $$$x$$$ и $$$y$$$ выпишем число $$$|x-y|$$$, а затем найдем количество различных чисел среди выписанных.

Например, для матрицы $$$\begin{pmatrix} 1 & 3\\ 4 & 2 \end{pmatrix}$$$ будут выписаны числа $$$|1-3|=2$$$, $$$|1-4|=3$$$, $$$|3-2|=1$$$ и $$$|4-2|=2$$$; среди них $$$3$$$ различных числа ($$$2$$$, $$$3$$$ и $$$1$$$), а значит, ее красота равна $$$3$$$.

Ваша задача — для заданного $$$n$$$ найти матрицу целых чисел размера $$$n \times n$$$, где каждое число от $$$1$$$ до $$$n^2$$$ встречается ровно один раз, такую, что ее красота максимально возможная среди всех таких матриц.