E. Subsequence Not Substring

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$.

Sample Input

4
bbacb
aaabaaba
gugguggguggggu
zzzzzzzzzzzzzzzz

Sample Output

ab
aaaa
ggggg
-1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）