Задача Лойда
Сэм Лойд — крупнейший американский мастер головоломок. Одна из самых известных его головоломок — это "Игра в пятнадцать". Также он известен как автор множества шахматных задач и задач на разрезание. Вам предлагается решить задачу Лойда про разрезание шахматной доски.
Задана шахматная доска размером n×n. Требуется распилить её на наибольшее количество частей так, чтобы любые две части были различны. Каждая часть должна состоять из одной или нескольких клеток и представлять собой связную по стороне фигуру. Части, отличающиеся только поворотом, считаются одинаковыми. Так, существует две одноклеточных части: черная клетка и белая клетка, и только одна часть, состоящая из двух клеток.
Вот одно из решений оригинальной задачи Лойда про разрезание обычной шахматной доски 8×8 на 18 различных частей:
Входные данные
В единственной строке содержится целое число n, длина стороны доски (1 ≤ n ≤ 30).
Выходные данные
В первой строке выведите максимальное количество частей, на которое можно разрезать доску. Далее выведите само разрезание: n строк по n маленьких латинских букв в каждой. Каждая часть должна состоять из одинаковых букв, при этом одну и ту же букву можно использовать для обозначения нескольких частей, но любые две соседние части должны состоять из разных букв. Если существует более одного оптимального разрезания, то можно вывести любое.