It was the start of a new TV series GOT directed by George RR Martin. The common thing with every season was that a character got killed at the end of season. Now, it was time for Ned Stark to die and he had to save his life. Although, Joffery was a cruel king but he gave Ned a last chance to save his life. He gave him a task on strings. The problem was that Ned was given a string and he had to rearrange the characters of the string (if necessary) and partition the string into k equally sized palindromes. But, Ned was not able to solve the problem so he asked his daughter, Sansa for help.

After a while, Joffery learned from his secret sources that Sansa was helping Ned in solving his task and so he decided to make the problem more interesting. Now, he ordered Ned to maximize the value of k and print k equally sized palindromes in lexicographical order.

You are Sansa's closest friend and she asks you to help save her father from being executed.

Input:

First line of the input consists of the no. of testcases t.
Each test case consists of a string s.
String consists of lowercase letters only.

Constraints:

1<=t<=100
1<=|s|<=100000

Output:

For every test case print two lines. In first line print the value of k and in next line print k equally sized palindromes in lexicographical order.