Encryption System

A programmer built a new encryption system. The system has a flaw: two or more different strings can encrypt to the same string.

You have one string that the system encrypted. To recover the original, you want to list every candidate for the string before encryption. Write a program that does this.

Encryption applies the following steps, in order, to a string made only of lowercase letters ('a' to 'z').

1. Change the first 'b' to 'a'. If there is no 'b', do nothing.
2. Change the first 'c' to 'b'. If there is no 'c', do nothing.
3. ...
4. Change the first 'z' to 'y'. If there is no 'z', do nothing.

Each step works on the string left by the previous step. A candidate is also a string made only of lowercase letters.

The input has at most 100 datasets. Each dataset is one line holding an encrypted string. The encrypted string is made only of lowercase letters, and its length is at least 1 and at most 20.

The input ends with a line holding a single '#'.

For each dataset, first print the number of candidates $n$ for the string before encryption on its own line, then print the candidates one per line. If $n$ is at most 10, print every candidate in dictionary order. Otherwise print the first five and the last five in dictionary order. If $n$ is 0, print only the 0.

Dictionary order is defined recursively. The empty string comes first in dictionary order. For two nonempty strings $x = x_1 \dots x_k$ and $y = y_1 \dots y_l$, the string $x$ precedes the string $y$ in dictionary order if one of the following holds.

• $x_1$ precedes $y_1$ in alphabetical order ('a' to 'z').
• $x_1$ and $y_1$ are the same character, and $x_2 \dots x_k$ precedes $y_2 \dots y_l$ in dictionary order.