Sam Loyd is a famous american puzzle creator. One of his most famous puzzles is “The 15 puzzle”. Also he is an author of many chess puzzles and cutting problems. Now you can try to solve his problem about cutting a chessboard.
You are given an n × n chessboard. Your goal is to cut it into the maximal number of pieces so that any two pieces are different. Each piece must consist of one or more cells and represent a side-connected region. If one piece can be obtained from another by a sequence of rotations then these pieces are considered equal. For example, there are two one-cell pieces: black cell and white cell and only one two-cell piece.
Here is one of possible solutions of the original Loyd's problem about cutting an 8 × 8 chessboard in 18 different pieces:
The first line contains the only integer n, the length of the chessboard side (1 ≤ n ≤ 30).
In the first line output the maximal number of different pieces the chessboard can be cut into. Then output the required cutting: n lines with n lowercase latin letters in each of them. Each piece must consist of the same letters, one letter can be used for representing several pieces, but every two pieces sharing a common side must be represented by different letters (see example for further clarification).
If there are several optimal cuttings, you can output any of them.
Problem Author: Sam Loyd feat. Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009