Problem Background

A challenging problem from a simulation contest that stumped me.

Problem Description

On a triangular grid, each small triangle has an area of 1. You can start from a point and walk along the edges to form a polygon that encloses a certain area. We can define five directions for each point:

a - Turn 120° left

b - Turn 60° left

c - Go straight

d - Turn 60° right

e - Turn 120° right

In this way, a shape can be represented by a sequence of letters. For example, the left diagram, starting from point A and moving clockwise, can be represented as dcddeaddd; starting from point B and moving clockwise, it can be represented as ddeaddddc; and so on. The right diagram shows the mirrored version of the left diagram.

The left and right diagrams are essentially the same shape. To uniquely represent a class of congruent shapes, we find the lexicographically smallest representation among all possible representations of that shape. The smallest representation for both the left and right diagrams is addddcdde.

Given a representation of a shape (not necessarily the smallest representation), you are asked to find the number of valid shapes that can be formed by adding one small triangle to this shape, and their smallest representations.

A shape is valid if and only if all its small triangles have at least one edge in common with another triangle, and there are no hollow spaces.

The following shapes are invalid:

Input Format

The first line contains a number T, representing the number of test cases.

The next T lines each contain a string, representing a representation of a shape.

The input data guarantees that the shape is valid and the representation is clockwise.

Output Format

For each test case:

The first line contains an integer K, representing the number of non-congruent shapes that can be formed by adding one small triangle.

The next line contains K strings, representing the smallest representations of these K different shapes (sorted lexicographically), separated by spaces. The smallest representations must be clockwise.

A blank line separates each pair of test cases.

Sample Input and Output

Input Sample #1

2
eee
cedde

Output Sample #1

1
dede

3
beddde cdecde cecece

Input Sample #2

2
adeccecced
dddddd

Output Sample #2

5
acedccecced addebcecced adebebecced adecbedcced cceccecce

1
cddddce

Notes

Sample Explanation

Explanation for Sample 1:

见题面 Input 部分

见题面 Output 部分