В этой задаче мы будем иметь дело с таблицами размера n × n, заполненными целыми числами от 1 до n² таким образом, чтобы выполнялись следующие условия.

1. Каждое число встречается в таблице ровно один раз.
2. Для каждого i от 2 до n² ячейки таблицы с числами i и i − 1 должны иметь общую сторону.

Будем называть простотой столбца количество простых чисел в нём, а простотой таблицы — максимальную простоту всех её столбцов. Найдите среди всех таблиц, удовлетворяющих приведённым условиям, таблицу с максимальной простотой.

В единственной строке записано целое число n (1 ≤ n ≤ 256).

Выведите искомую таблицу. Если существует несколько таблиц с максимальной простотой, выведите любую из них.

Простота таблицы в примере равна 3 (это простота её первого столбца).