eolymp
bolt
Try our new interface for solving problems
Problems

Loyd`s Problem

Loyd`s Problem

Time limit 1 second
Memory limit 16 MiB

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:

Input data

The first line contains the only integer n, the length of the chessboard side (1n30).

Output data

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.

Examples

Input example #1
8
Output example #1
18
aabbaaab
aacbbdab
bcccdddb
baaacccb
bbczzacd
acazzaad
acczzbcd
aaczzbcc
Author Sam Loyd, Igor Chevdar
Source Ural SU Contest. Petrozavodsk Winter Session, February 2009