素数是一个正整数,它恰好有两个不同的正因数:$$$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