Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

B. Shohag любит строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для строки $$$p$$$ определим $$$f(p)$$$ — количество уникальных непустых подстрок$$$^{\text{∗}}$$$ строки $$$p$$$.

У Shohag есть строка $$$s$$$. Помогите ему найти непустую строку $$$p$$$, такую, что $$$p$$$ является подстрокой $$$s$$$, а $$$f(p)$$$ чётно, или скажите, что такой строки не существует.

$$$^{\text{∗}}$$$Строка $$$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
Примечание

В первом наборе входных данных мы можем выбрать $$$p = $$$ abaa, потому что это подстрока $$$s$$$, а уникальными подстроками $$$p$$$ являются a, b, aa, ab, ba, aba, baa и abaa — всего $$$8$$$ уникальных подстрок, что является чётным числом.

Во втором наборе входных данных мы можем выбрать только $$$p = $$$ a, но у этой строки есть одна уникальная подстрока, что является нечётным числом, поэтому эта строка не подходит.

В третьем наборе входных данных вся строка содержит $$$52$$$ уникальных подстроки, поэтому сама строка является корректным ответом.