← 返回题目列表

Codeforces · 1861/A

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

输出 #1

167
53
3571
57638429