← 返回题目列表

Codeforces · 1562/B

B. 记忆中的场景

中文机器翻译题面 查看原题

在催眠过程中,尼古拉斯突然想起了一个正整数$$$n$$$,它不包含十进制的零。

很快,当他回到家时,他很好奇:最多可以从数字中删除多少位数字,使该数字成为非素数,即不是合数或等于一?

对于某些数字,这样做是不可能的:例如,对于数字$$$53$$$,不可能删除其某些数字来获得非素数。然而,对于这个问题的测试用例中的所有$$$n$$$,保证可以删除其中的一些数字以获得非素数。

请注意,您无法删除号码中的所有数字。

素数是除了 1 和它本身之外没有约数的数字。合数是具有两个以上除数的数字。 $$$1$$$ 既不是质数也不是合数。

输入

每个测试包含多个测试用例。

第一行包含一个正整数$$$t$$$ ($$$1 \le t \le 10^3$$$),表示测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个正整数 $$$k$$$ ($$$1 \le k \le 50$$$) — 数字中的位数。

每个测试用例的第二行包含一个正整数 $$$n$$$,不包含十进制表示的零 ($$$10^{k-1} \le n < 10^{k}$$$)。保证总是可以删除少于 $$$k$$$ 的数字以使该数字不是质数。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$10^4$$$。

输出

对于每个测试用例,在两行中打印两个数字。在第一行中打印您在号码中留下的位数。在第二行中打印所有删除后留下的数字。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

7
3
237
5
44444
3
221
2
35
3
773
1
4
30
626221626221626221626221626221

输出 #1

2
27
1
4
1
1
2
35
2
77
1
4
1
6

注意

在第一个测试用例中,您无法从数字 $$$237$$$ 中删除 $$$2$$$ 数字,因为所有数字 $$$2$$$、$$$3$$$ 和 $$$7$$$ 都是质数。但是,您可以删除 $$$1$$$ 数字,得到数字 $$$27 = 3^3$$$。

在第二个测试用例中,您可以删除除一位之外的所有数字,因为 $$$4 = 2^2$$$ 是一个合数。