删除一个数字 - 题目

Busy Beaver 非常喜欢合数。有一天，他在黑板上看到一个数字，想在不改变太多的情况下将其变为合数。

给定一个正整数 $N$，其所有数位均为 $1$ 或 $2$。

从 $N$ 中最多删除一个数位（也可以保持 $N$ 不变），使得 $N$ 变为合数。你不能重新排列未删除的数位。为了证明你得到的新数字是合数，你还需要输出它的一个非平凡因子。

如果正整数 $d$ 是正整数 $n$ 的非平凡因子，则意味着 $n$ 是 $d$ 的倍数，且 $d \neq 1$ 且 $d \neq n$。

第一行包含一个正整数 $T$ ($1 \le T \le 200$)，表示测试用例的数量。

每个测试用例包含一行：一个正整数 $N$ ($10^3 < N < 10^{200}$)，仅由数字 $1$ 和 $2$ 组成。

对于每个测试用例，输出一行，包含两个由空格分隔的数字。

首先输出一个正整数 $M$，使得 $M = N$ 或者 $M$ 是从 $N$ 中删去一个数位后得到的数字。然后输出一个正整数 $K$，使得 $M$ 是 $K$ 的倍数且 $1 < K < M$。

可以证明，在题目给定的约束条件下，解总是存在的。如果存在多个可能的 $M$ 和/或 $K$ 值，任何合法的组合都将被接受。

4
121212
11121
12211
212221112112211

121212 10101
1121 59
2211 67
21221112112211 4933994911

在第一个样例测试用例中，$121212$ 本身就是合数，因此我们不需要删除任何数位，并可以输出它的一个非平凡因子。$10101$ 是一种可能，因为 $121212 = 12 \cdot 10101$。

在第二个样例中，我们可以删除第一个 $1$ 将数字变为 $1121$，它是合数，因为 $1121 = 19 \cdot 59$，输出 $19$ 或 $59$ 均可。我们也可以保持 $11121$ 不变；如果这样做，可能的答案包括 11121 33 和 11121 337。

在第三个样例中，$12211$ 是质数，因此我们必须删除一个数位。其他可能的解包括 1211 7 和 1221 37。

QOJ.ac