Сэм Лойд — крупнейший американский мастер головоломок. Одна из самых известных его головоломок — это «Игра в пятнадцать». Также он известен как автор множества шахматных задач и задач на разрезание. Вам предлагается решить задачу Лойда про разрезание шахматной доски.

Задана шахматная доска размером n × n. Требуется распилить её на наибольшее количество частей так, чтобы любые две части были различны. Каждая часть должна состоять из одной или нескольких клеток и представлять собой связную по стороне фигуру. Части, отличающиеся только поворотом, считаются одинаковыми. Так, существует две одноклеточных части: черная клетка и белая клетка, и только одна часть, состоящая из двух клеток.

Вот одно из решений оригинальной задачи Лойда про разрезание обычной шахматной доски 8 × 8 на 18 различных частей:

В единственной строке содержится целое число n, длина стороны доски (1 ≤ n ≤ 30).

В первой строке выведите максимальное количество частей, на которое можно разрезать доску. Далее выведите само разрезание: n строк по n маленьких латинских букв в каждой. Каждая часть должна состоять из одинаковых букв, при этом одну и ту же букву можно использовать для обозначения нескольких частей, но любые две соседние части должны состоять из разных букв. Если существует более одного оптимального разрезания, то можно вывести любое.