Олимпиадный тренинг

Задача . A. Простое удаление


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

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

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

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

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

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

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

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

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

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

  • если невозможно получить простое число описанными в условии операциями, выведите \(-1\);
  • иначе выведите любую последовательность цифр, которая соответствует простому числу и которую можно получить, проведя описанную в условии операцию несколько (возможно, ноль) раз. Если есть несколько различных последовательностей, выведите любую из них.

Примеры
Входные данныеВыходные данные
1 4
123456789
987654321
243567918
576318429
167
53
3571
57638429

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python1
С++ Mingw-w643
Комментарий учителя