排列与合数

题目描述

小 A 在 2023 年某场 CCPC 大学生程序设计竞赛的赛场上遇到了一道名为 “排列与质数” 的题目。

与大多数选手一样，小 A 并没能在赛场上解决这个棘手的题目。比赛结束后，小 A 想到了一个与之相关的题目：排列与合数，可是小 A 仍然没有能力解决。这个名为 “排列与合数” 的题目是这样的：

给定一个有且仅有 $5$ 位，且各个数位互不相同的十进制正整数 $n$。你可以重新排列 $n$ 的各个数位，但需要保证重新排列得到的整数 $n′$ 没有前导零。请问重新排列数位得到的 $n′$ 能否为合数？若能为合数，请求出一个满足条件的 $n′$。

例如，当 $n = 12345$ 时，任意排列得到的 $n′$ 均是合数，因此可以任意取 $n′$。当 $n = 13579$时，可以重新排列数位得到合数 $n′ = 97531 = 7 × 13933$。

现在，小 A 带着他的题目来到赛场上求助。你能帮助小 A 解决这个题目吗？

一个正整数是合数，当且仅当它可以分解为两个不小于 $2$ 的整数的乘积。

输入格式

本题测试点包含多组数据。 第一行，一个正整数 $T（1 ≤ T ≤ 10^5）$，表示数据组数。 对于每组数据： 一行，一个正整数 $n（10^4 ≤ n < 10^5）$，保证 $n$ 的各个数位互不相同。

输出格式

对于每组数据： 输出一行，一个整数。若能重新排列 $n$ 的数位得到合数 $n′$ 则输出 $n′$，否则输出 $−1$。

样例 #1

样例输入 #1

5
12345
12345
12345
12345
13579

样例输出 #1

12345
54321
13524
45123
97531