Largest Permutated Palindrome

You are given an integer \(n\). Your task is to find the largest palindromic number that can be formed by permuting the digits of \(n\) such that the resulting number is less than or equal to \(n\). In other words, if we denote the palindromic number by \(P\), it must satisfy:

[ P \le n ]

and \(P\) must be a palindrome, i.e. it reads the same forwards and backwards.

If no such palindromic number exists, output -1.

Note: All digits of \(n\) must be used exactly once to form \(P\). You can assume that \(n\) does not contain any leading zeros.

inputFormat

The first line contains a single integer \(T\), the number of test cases. Each of the following \(T\) lines contains one integer \(n\).

For example:

3
32123
12345
9876

outputFormat

For each test case, output a single line with the largest palindromic number that can be formed by permuting the digits of \(n\) such that it is less than or equal to \(n\). If no such number exists, output -1.

For the sample input above, the correct output is:

32123
-1
-1

## sample

3
32123
12345
9876

32123
-1
-1

</p>