Problem Description

Given a string $S$ consisting of only lowercase latin letters。

Find the lexicographic smallest string $T$, satisfying $T$ is a subsequence of $S$, but $T$ is not a substring of $S$, or determine such $T$ doesn't exist.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 2 \times 10 ^ 5$) - the number of test cases. Description of the test cases follows.

The first line of each test case contains one string $S$ ($1 \le \lvert S \rvert \le 10 ^ 5$).

It's guaranteed that $\sum \lvert S \rvert \le 5 \times 10 ^ 6$.

Output

For each test case, print a single string $T$, satisfying $T$ is a subsequence of $S$, but $T$ is not a substring of $S$. If such $T$ doesn't exist, print `-1`.

It's guaranteed that $\sum \lvert T \rvert \le 2 \times 10 ^ 6$.

4
bbacb
aaabaaba
gugguggguggggu
zzzzzzzzzzzzzzzz

ab
aaaa
ggggg
-1