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