You are given a string \(S\) containing only lowercase alphabets. You can swap two adjacent characters any number of times (including 0).

A string is called anti-palindrome if it is not a palindrome. If it is possible to make a string anti-palindrome, then find the lexicographically smallest anti-palindrome. Otherwise, print \(-1\).

Input format

The first line contains a single integer \(T\) denoting the number of test cases. The description of \(T\) test cases follows.
Each line contains a string \(S\) of lower case alphabets only.

Output format

For each test case, print the answer in a new line.

Constraints

\(1 \leq T \leq 100 \)

\(2 \leq |S| \leq 2 \times 10^5\)

\(S\) contains only lowercase alphabets.