题目描述

对于字符串 $p$，设 $f(p)$ 是 $p$ 的非空子串的个数。

小田有一个字符串 $s$，现在请你从中找出一个非空字符串 $p$，使得 $p$ 是 $s$ 的子串，并且 $f(p)$ 是偶数。如果 $s$ 中不存在这样的子串，输出 $-1$。

子串的概念为：若 $a$ 可以从 $b$ 中删除开头的任意个字符和结尾的任意个字符，那么 $a$ 就是 $b$ 的子串。

输入

第一行包含一个整数 $t$，代表测试样例的组数。 ($1 \le t \le 10^4$)

对于每组测试样例：

输入一行，一个由小写英文字母组成的字符串 $s( 1 \le |s| \le 10^5)$

数据保证所有的 $|s|$ 总和不超过$3 \cdot 10^5$.

输出

对于每组测试样例，输出任意一个满足条件的字符串，如果不存在这样的字符串，则输出 $-1$。

5
dcabaac
a
youknowwho
codeforces
bangladesh

abaa
-1
youknowwho
eforce
bang