Statement

For a string $p$ , let $f(p)$ be the number of distinct non-empty substrings $^{\text{∗}}$ of $p$ .

Shohag has a string $s$ . Help him find a non-empty string $p$ such that $p$ is a substring of $s$ and $f(p)$ is even or state that no such string exists.

$^{\text{∗}}$ A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Format

Input

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

The first and only line of each test case contains a string $s$ ( $1 \le |s| \le 10^5$ ) consisting of lowercase English letters.

It is guaranteed that the sum of the length of $s$ over all test cases doesn't exceed $3 \cdot 10^5$ .

Output

For each test case, print a non-empty string that satisfies the conditions mentioned in the statement, or $-1$ if no such string exists. If there are multiple solutions, output any.

Sample

5
dcabaac
a
youknowwho
codeforces
bangladesh

abaa
-1
youknowwho
eforce
bang