Palindromic Cut

Phile has a string s of length n consisting of lowercase and uppercase Latin letters and digits.

He wants to rearrange the symbols in s and then cut it into the minimum number of parts so that each part is a palindrome and all parts have the same lengths. A palindrome is a string which reads the same backward as forward, such as [madam] or [racecar].

Please help Phile and determine the minimum number of palindromes of equal lengths to cut s into, if it is allowed to rearrange letters in s before cuttings.

Input starts with an integer T(T<=50), denoting the number of test cases.
For each case:
The first line contains an integer n(1 ≤ n ≤ 100000) — the length of string s.
The second line contains a string s of length n consisting of lowercase and uppercase Latin letters and digits.

For each test case:
Print to the first line an integer k — minimum number of palindromes into which you can cut a given string.
Print to the second line k strings — the palindromes themselves. Separate them by a space. All of them should have the same length.
You are allowed to print palindromes in arbitrary order. And if there are multiple solutions, print any of them.

3
6
aabaac
8
0rTrT022
2
aA
2
aba aca
1
02TrrT20
2
a A

2017 fdu-icpc

2017 Fudan ACM-ICPC 程序设计校赛现场赛