SP5144 CRYPTO6 - Cryptography Reloaded (Act I)

ICPC（密码编程与计算研究所）的研究人员在闲暇时都在做些什么呢？没错，除了在在线评测系统上解决算法问题，他们还常常研究各种密码方案。最近，研究员Tom对手持设备中的RSA算法实现产生了浓厚的兴趣。 RSA算法的基本原理如下： 1. 选择两个不同的素数 $p$ 和 $q$，令 $n = p \times q$； 2. 选择一个整数 $e$，使得 $\gcd(e, (p - 1)(q - 1)) = 1$； 3. 计算整数 $d$，满足同余关系 $de \equiv 1 \pmod{(p - 1)(q - 1)}$。 这样，当某人A希望另一个人B以加密方式传递消息给他时，A可以按照上述步骤生成他的公钥 $(n, e)$ 并公开。接收到A的公钥后，B只需通过计算 $y = x^e \mod n$ 来加密消息 $x$（使得 $0 \le x < n$）。这样生成的加密消息理想状态下只有A能够使用他的私钥 $d$ 解密，即 $x = y^d \mod n$。 考虑到手持设备的计算能力通常有限，因此加密时常使用较小的 $e$ 值，这可能导致安全风险。例如，当同时拥有公钥 $(n, e)$ 和私钥 $d$ 时，恢复诸如 $p$ 和 $q$ 的素数（即分解 $n$）是较为简单的过程。你能帮助Tom编写一个程序来演示这一过程吗？

输入文件包含多个测试用例。 每个测试用例由三个整数 $n$、$d$ 和 $e$ 组成（$n \le 10^{100}, 3 \le e \le 31$）。请注意，这些数没有前导零，并且满足题中的条件。 两个连续的测试用例之间用一个空行分隔。当出现 $n = 0$、$d = 0$ 和 $e = 0$ 时，表示输入结束，此时程序不应进行处理。

对于每个测试用例，请输出两个素数 $p$ 和 $q$，使得 $n = pq$ 且 $p < q$： ``` Case #X: p q ``` 其中 `X` 是测试用例的编号（从1开始），`p` 和 `q` 是满足条件的素数。

- $n \le 10^{100}$ - $3 \le e \le 31$ **本翻译由 AI 自动生成**