#201380. 三角形图

请在 这里 查看原题面。

UNowen 有 个平面向量 ，其中：

• ；
• ；
• 对于任意正整数 ，总存在整数 使得 ；（）
• 除了整个向量序列以外（下同），向量序列中不存在和为 的一段。

此处 代指「将 旋转至与 同向所旋转的角度」，逆时针为正角，顺时针为负角（例如，设 ，，则 ）。

也就是说，这 个向量的长度（模）均为 ，并且首尾拼接可以得到一个封闭多边形。保证这个封闭多边形的各个内角均为 的正整数倍，内部没有其他向量，并且不是空心的。

为了表述方便，我们用一个长度为 ，字符集为 的字符串 来描述 。

具体地，对于 的第 个字符（特别地， 等价于 ， 等价于 ，下同）：

此外，UNowen 按如下方式定义一个向量序列 的「标准表示」：

• 分别对于 ，求出向量序列 对应的字符串：
• 取 个字符串中字典序最小的字符串作为向量序列 的「标准表示」。

例如，上图中向量序列的「标准表示」是 ，而不能是 。

现在，UNowen 把向量序列 对应的字符串 （不一定是「标准表示」）给了你。他希望你可以按如下方式对这个向量序列进行一次修改：

• 选定一个正整数 ；
• 构造两个平面向量 ，使得：
  • ；
  • ；
  • ；
  • 。
• 用 两项（ 在前， 在后）替换 ；
• 若 ，删除 ；
• 若 ，删除 ；
• 若修改后的向量序列中存在和为 的一段（除了整个向量序列以外），那么 UNowen 称这次修改是不合法的。例如，在下面的图片中，如果选择 ，那么修改就是不合法的。
• UNowen 会将修改后的向量序列的「标准表示」定义为该次修改的「修改结果」。
• 对于任意两个修改方案，如果修改后的向量序列首尾拼接得到的图形全等，那么 UNowen 会认为这两个修改方案是等价的。例如，在下面的图片中， 和 的两个修改方案就是等价的。
• 也就是说，修改操作会对封闭多边形上的某个向量向外作等边三角形，使得修改后的图形仍为满足上述要求（各个内角均为 的正整数倍，内部没有其他向量，并且不是空心的）的封闭多边形。对于任意两个修改方案，如果修改后的向量序列首尾拼接得到的图形全等，那么它们是等价的。

请求出互不等价的合法的修改方案的个数，并按字典序从小到大输出每个修改方案的「修改结果」。

本题有多组数据。

第一行一个正整数 ，表示数据组数。

下面 行，每行一个字符集为 的非空字符串 。保证 不会出现。

对于每组数据，输出三行：

第一行一个正整数 ，表示，并按字典序从小到大输出每个修改方案。

第二行 个字符集为 的非空字符串（用空格隔开），表示每个可能出现的「修改结果」。你需要按字典序从小到大的顺序输出它们。可以证明 不会出现。

第三行是空行。请特别注意这一点，因为它不符合传统题的一般数据格式。

样例输入 1

2
eee
cedde

样例输出 1

1
dede

3
beddde cdecde cecece

样例输入 2

2
adeccecced
dddddd

样例输出 2

5
acedccecced addebcecced adebebecced adecbedcced cceccecce

1
cddddce

样例输入 3

7
eee
cedde
adeccecced
dddddd
ccdeccde
baedddcdde
abcedcdcddde

样例输出 3

1
dede

3
beddde cdecde cecece

5
acedccecced addebcecced adebebecced adecbedcced cceccecce

1
cddddce

4
bcdeccdde bcedccece bdeccdebe cccedccde

8
abdecdcddde abececcddde abedcebddde abeddbecdde abeddccecde abeddcdcece abeddcddced addddcdde

10
abbeddcdcddde abcdeccdcddde abcecebdcddde abcedbeccddde abcedccebddde abcedcdbecdde abcedcdccecde abcedcdcdcece abcedcdcddced acedcdcdddd

设 为字符串 的长度。

对于 的数据，，。

对于 的数据，保证所有的修改方案都是合法的。

对于 的数据，，。