题目描述

质数是指恰好有两个不同正因数（$1$ 和它本身）的正整数。例如，$2$、$3$、$13$ 和 $101$ 是质数；$1$、$4$、$6$ 和 $42$ 不是质数。

现在给你一个由 $1$ 到 $9$ 组成的数字序列，其中每个数字从 $1$ 到 $9$ 恰好出现一次。

你可以进行如下操作若干次（也可以一次都不做）：从序列中选择任意一个数字并将其删除。但是，如果序列中只剩下两个数字，则不能再进行此操作。

你的目标是得到一个表示质数的序列。注意，你不能改变序列中数字的顺序。

请输出最终得到的序列，或者报告无法通过上述操作得到一个质数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。

每个测试用例包含一行，由 $9$ 个数字组成的字符串（中间没有其他字符）。该字符串中每个数字 $1$ 到 $9$ 恰好出现一次。

输出格式

对于每个测试用例，输出一行答案：

• 如果无法通过上述操作得到一个质数，输出 $-1$；
• 否则，输出任意一个可以通过上述操作得到的、表示质数的序列。如果有多个满足条件的序列，可以输出其中任意一个。

说明/提示

由 ChatGPT 4.1 翻译

样例

4
123456789
987654321
243567918
576318429

167
53
3571
57638429