A. Простое удаление
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Простое число — это положительное целое число, у которого ровно два различных положительных делителя: $$$1$$$ и само число. Например, $$$2$$$, $$$3$$$, $$$13$$$ и $$$101$$$ — простые числа; $$$1$$$, $$$4$$$, $$$6$$$ и $$$42$$$ не являются простыми числами.

Вам задана последовательность цифр от $$$1$$$ до $$$9$$$, в которой каждая цифра от $$$1$$$ до $$$9$$$ встречается ровно один раз.

Вы можете применять следующую операцию несколько (возможно, ноль) раз: выбрать любую цифру из последовательности и удалить ее. Однако вы не можете применять эту операцию, если в последовательности осталось только две цифры.

Ваша цель — получить последовательность цифр, являющуюся простым числом. Обратите внимание, что менять порядок цифр нельзя.

Выведите итоговую последовательность или сообщите, что получить простое число описанными в условии операциями невозможно.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей $$$9$$$ цифр (без символов-разделителей между ними). Каждая цифра от $$$1$$$ до $$$9$$$ входит в эту строку ровно один раз.

Выходные данные

Для каждого набора входных данных выведите ответ в отдельной строке следующим образом:

  • если невозможно получить простое число описанными в условии операциями, выведите $$$-1$$$;
  • иначе выведите любую последовательность цифр, которая соответствует простому числу и которую можно получить, проведя описанную в условии операцию несколько (возможно, ноль) раз. Если есть несколько различных последовательностей, выведите любую из них.
Пример
Входные данные
4
123456789
987654321
243567918
576318429
Выходные данные
167
53
3571
57638429