对于字符串 $$$p$$$,令 $$$f(p)$$$ 为 $$$p$$$ 的不同非空子串 $$$^{\text{*}}$$$ 的数量。
Shohag 有一个字符串 $$$s$$$。帮助他找到一个非空字符串 $$$p$$$,使得 $$$p$$$ 是 $$$s$$$ 的子串,并且 $$$f(p)$$$ 是偶数,或者说明不存在这样的字符串。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行也是唯一一行包含一个由小写英文字母组成的字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$)。
保证所有测试用例$$$s$$$的长度总和不超过$$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个满足语句中提到的条件的非空字符串,如果不存在这样的字符串,则打印 $$$-1$$$。如果有多个解,则输出任意一个。
示例
输入 #1
5 dcabaac a youknowwho codeforces bangladesh
输出 #1
abaa -1 youknowwho eforce bang
注意
在第一个测试用例中,我们可以设置$$$p = $$$ abaa,因为它是$$$s$$$的子串,并且$$$p$$$的不同非空子串是a、b、aa、ab、ba、aba、baa和abaa,因此它总共有$$$8$$$不同子串,并且是偶数。
在第二个测试用例中,我们只能设置 $$$p = $$$ a 但它有一个不同的非空子字符串,但这个数字是奇数,因此无效。
在第三个测试用例中,整个字符串包含 $$$52$$$ 不同的非空子字符串,因此字符串本身是一个有效的解决方案。