섞인 출력

시간 제한3초메모리 제한1024 MB

요약

S가 같은 문자열 N개를 섞어 만든 결과일 때, 원래 문자열이 될 수 있는 것을 모두 사전순으로 출력합니다.

난이도: 보통10점 중 6점
유형: 백트래킹, 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

유쿠는 여러 가지 명령줄 프로그램을 실험했다. 대부분의 프로그램은 같은 프로그램을 여러 번 연속으로 실행하면 매번 같은 출력을 냈다. 예를 들어 pwd 프로그램을 두 번 연속 실행하면 다음과 같이 출력된다.

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

하지만 같은 프로그램을 여러 개 동시에 실행하면 출력이 서로 섞인다. 유쿠가 pwd 두 개를 동시에 실행했을 때는 실행할 때마다 다른 결과가 나왔다.

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

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

서로 다른 실행 인스턴스의 문자는 섞일 수 있지만, 각 인스턴스의 출력은 전부 빠짐없이 나오며 한 인스턴스가 낸 문자들은 원래 순서를 유지한다. 유쿠는 이 현상을 더 실험하려 했지만, 일부 프로그램의 출력은 알 수 없었다. 이제 주어진 정보로 가능한 출력을 모두 복원하려 한다.

입력

입력은 여러 개의 테스트케이스로 구성될 수 있다. 첫 줄에 테스트케이스의 개수 $T$ ( $1 \le T \le 20$ )가 주어진다.

각 테스트케이스는 두 줄로 이루어진다. 첫 줄에는 동시에 실행한 프로그램의 개수 $N$ ( $2 \le N \le 10$ )이 주어진다. 둘째 줄에는 같은 프로그램의 $N$ 개 인스턴스를 동시에 실행했을 때 얻은 출력 문자열 $S$ 가 주어진다. $S$ 는 영어 소문자로만 이루어지며, 공백, 줄바꿈, 그 밖의 특수 문자는 없다.

한 인스턴스의 출력 길이를 $L$ 이라 하면 $S$ 의 길이는 $N \cdot L$ 이다. 각 테스트케이스에서 $N^L \le 2 \cdot 10^7$ 이 보장된다. 아래 표는 $N$ 별 최대 $L$ 값이다.

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

출력

각 테스트케이스마다 두 줄을 출력한다. 첫 줄에는 가능한 출력의 개수를 출력한다. 둘째 줄에는 가능한 출력을 모두 공백으로 구분하여 사전순으로 출력한다.

테스트케이스에 따라 가능한 출력이 하나뿐인 경우도 있고, 여러 개인 경우도 있다.

예제1

예제 1

입력

4
2
abcdabcd
5
aaaaaaaaaa
2
aabbaabb
4
eerrrroereorrrorrror

예상 출력

1
abcd
1
aa
2
aabb abab
1
error