A lattice of triangles - cf the picture below - is built of equilateral triangles of side 1.

A path in a lattice of triangles is a name for any finite sequence of triangles (of side 1) of the lattice, such that every two consecutive triangles in the sequence have a common side.

A figure made of points of a finite number of lattice triangles is called an island, if any two triangles contained in it can be connected by a path composed of that figure's triangles.

Example

The figures presented on the pictures 1.1, 1.2 and 1.3 are islands. The figure on the picture 1.4 is not an island. Figures on the pictures 2.2, 2.3 and 2.5 are congruent.

For every n <= 10 we intend to describe systematically all non-congruent islands which may be made of n triangles of side 1, and to count them.

A coast of every island built of at most 10 triangles is a closed broken line, consisting of unitary segments, and it may be circulated (contoured round without taking the pencil off the paper) in such a way that we run along every segment of the coast exactly once and get back to the starting point. It may happen that it is necessary to go more than once through a particular point - cf e.g. the picture 2.4.

In the case of islands built of at most 10 triangles, it is not possible to get a situation such as the one presented on the picture 1.2, i.e. the coast of that figure consists of two separate parts and it cannot be circulated.

While circulating a coast, after every unitary segment we turn:
a - by 120 degrees to the left, or
b - by 60 degrees to the left, or
c - by 0 degrees (i.e. we actually do not turn), or
d - by 60 degrees to the right, or
e - by 120 degrees to the right.

Every circulation on an island coast can be described by means of a word composed of letters from the set {a, b, c, d, e}, marking by an appropriate letter a turn that is to be made after every successive unitary segment of the broken line forming the coast. A description of a circulation on an island coast has as many letters as there are unitary segments in the broken line forming the coast. We also note the turn after the last segment of the broken line, although it is not necessary to unambiguously determine its shape. This (in some sense redundant) letter makes it easier to transform the given description into a description of another circulation on the same figure, that starts in another point.

Examples

The words: cdddcddd, dcdddcdd and cbbbcbbb describe different circulations on the figure on the picture 2.1.

The words: cbeddcde, adcabcbb and abcbbadc describe different circulations on the island on the picture 2.2.

The words: acdabbcb and cddebced describe different circulations on the island on the picture 2.3.

If, while circulating on an island coast, we have its interior on the right-hand side, then we say that it is a clockwise circulation.

For every island a set of all congruent islands and their clockwise circulations may be identified.

An island code is a word which:

S1. is a description of some clockwise circulation on the coast of some congruent island,
S2. is prior in alphabetical order to all other words conforming to the condition S1.

Examples

For the congruent islands on the pictures 2.2 and 2.3 we consider all clockwise circulations on both:

beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde

and:

bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd,

and as the code for each of them we choose the word that in alphabetical order one should place in the first position: bcedcdde.

The word aadecddcddde is the code for the island presented on the picture 2.4.

Task

Write a program that successively for every input from the text file WYS.IN generates a collection of results and writes it to the text file WYS.OUT.

An input may be:

1. A word, which is a correct code of an island formed by at most 9 triangles, or
2. A positive integer not greater than 10.

The file WYS.IN is always nonempty and may contain many inputs. Consecutive inputs are written in separate lines, and immediately after the last one there is the end of the file.

We assume the file WYS.IN is faultless and the program needs not examine its correctness.

The file WYS.OUT should contain one collection of results for each input from the file WYS.IN.

There may be two kinds of result collections:

1. If the input is a code k, then the result is a sequence. Its first element is the number of different codes of islands that may be formed from any of congruent islands described by the code k, by adding one triangle of side 1 (not belonging to the island). Further elements are these codes in alphabetical order. Consecutive elements of the sequence are separated by a space or an end-of-line character.
2. If the input is a number n, then the result is also a sequence. Its first element is the number of different codes of islands, that can be formed from n lattice triangles of side 1. Next elements are these codes in alphabetical order. Consecutive elements of the sequence are separated by a space or an end-of-line character.

Consecutive result collections should be separated by an empty line. After the last collection there is the end of the file.

Example

For the file WYS.IN:

eee
adeccecced
5
dddddd
6(end of file)

1 dede
(empty line)
5
acedccecced addebcecced adebebecced adecbedcced cceccecce
(empty line)
4 aedddde bdecdde bececde ccedcde
(empty line)
1 cddddce
(empty line)
12
adecddde aececdde aedcecde bcedcdde
bddebdde bdebecde bdeccece bdecdced bebedcde
becebece ccdeccde dddddd(end of file)

At the beginning of your program, in a comment, give your last and first name, and the number of your working stand.

Your program should look for the file WYS.IN in the current directory and create the file WYS.OUT also in the current directory. The source file containing the program written by you should be named WYS.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file WYS.EXE. Both the files should be stored on a hard disk and on a floppy disk.

The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk, and of the description of your algorithm and the justification of its correctness.