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.