B. Spidey and the Palindrome Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thanos, the most feared villain in the universe, had conquered countless worlds. But there was one secret, one weakness that haunted him: the Palindrome Sequence. A mysterious force, ancient and powerful, had once foretold that a properly formed sequence of palindromes could undo his cosmic power.

Spidey stumbled upon this knowledge during a secret mission. He learned that the only way to shatter the invincibility of Thanos was to create a palindrome sequence. Since he was always out of school, he needs your help to defeat Thanos.

You are given a string $$$s$$$ of length $$$n$$$ containing lowercase letters.

A palindrome sequence is a sequence containing only palindromes of size $$$m$$$ $$$(m\ge2)$$$ and has at least $$$2$$$ palindromes. (All palindromes are of equal size)

Your task is to determine whether or not it is possible to defeat Thanos by creating a palindrome sequence by re-arranging the given string and if so, create a palindrome-sequence.

Input

The first line contains a single integer $$$t$$$ $$$(1\le t \le 10^4)$$$ — the number of testcases.

The only line of each testcase contains the string $$$s$$$ of size $$$n$$$ $$$(1\le n\le2\cdot10^5)$$$. Sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.

Output

For each testcase,

If possible,

  • Output two lines, the first line contains a single integer $$$m$$$ — the size of each palindrome in the sequence.
  • The second line contains the palindrome sequence obtained after re-arranging the given string $$$s$$$.

If not possible, output $$$-1$$$.

Example
Input
5
abbcca
abcabcabc
dotslash
racecar
deed
Output
2
ccaabb
3
bbbcccaaa
-1
-1
2
eedd
Note
  • In the first testcase, we can have a palindrome-sequence of $$$3$$$ palindromes i.e. aa, bb and cc. Hence, we first output the size of each palindrome, $$$2$$$ and then the palindrome-sequence ccaabb.
  • The second and fifth testcase is similar to the first testcase.
  • In the third and fourth testcase, there is no possible palindrome-sequence.