Mixed Output

Time limit3sMemory limit1024 MB

Summary

Given S made by interleaving N identical copies of one string, list every distinct string that could be that original copy, in lexicographic order.

Level: Medium6 of 10
Topics: Backtracking, Dynamic programming, String
Solved: No attempts yet

Problem

Juku tried various command-line programs. For most programs, running several copies one after another gave the same output each time. For example, running pwd twice in a row printed the following.

/home/juku/lahendused/segane
/home/juku/lahendused/segane

However, running several copies of the same program at once mixed their output together. When Juku ran two copies of pwd at the same time, he got a different result on each try.

/home//homjukue/ju/lahkeundu/sedl/ahseeganen
dused/segane

/h/ohomme/e/juku/lajukhue/landusehedn/segadunseed/
segane

The characters of different copies could interleave, but each copy's full output was printed completely, and the characters of one copy kept their original order. Juku wants to reconstruct all possible outputs from the information he has.

Input

The input may consist of several test cases. The first line contains the number of test cases $T$ ( $1 \le T \le 20$ ).

Each test case consists of two lines. The first line contains the number of programs $N$ ( $2 \le N \le 10$ ) run at the same time. The second line contains the string $S$ , the output obtained when $N$ copies of one program were run at the same time. For simplicity, $S$ consists only of lowercase Latin letters and contains no spaces, line breaks, or other special characters.

Let $L$ be the length of the output of one copy. Then $S$ has length $N \cdot L$ , and each test case guarantees $N^L \le 2 \cdot 10^7$ . The table below gives the maximum $L$ for each $N$ .

$N$	$\max{L}$
$2$	$24$
$3$	$15$
$4$	$12$
$5$	$10$
$6$	$9$
$7$	$8$
$8$	$8$
$9$	$7$
$10$	$7$

Output

For each test case, print two lines. The first line contains the number of possible outputs. The second line contains all possible outputs separated by spaces, in lexicographic order.

Some test cases have exactly one possible output, and others have several.

Examples1

Example 1

Input

4
2
abcdabcd
5
aaaaaaaaaa
2
aabbaabb
4
eerrrroereorrrorrror

Expected output

1
abcd
1
aa
2
aabb abab
1
error