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 sideconnected 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 onecell pieces: black cell and white cell and only one twocell piece.
Here is one of possible solutions of the original Loyd's problem about cutting an 8 × 8 chessboard in 18 different pieces:
Input
The first line contains the only integer n, the length of the chessboard side (1 ≤ n ≤ 30).
Output
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.
Sample
input  output 

8  18
aaaacaaa
bbbcccba
baddabbb
aacdacba
accdacaa
babdccbb
baaadbba
babbaaaa

Problem Author: Sam Loyd feat. Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009