描述

在数学中，Lucas–Lehmer 测试是一种针对 Mersenne 数（形如 $2^n - 1$ 的数）的素性检验。该测试最早由 Edouard Lucas 于 1856 年提出，后在 1878 年经 Lucas 改进，并在 1930 年代由 Derrick Henry Lehmer 进一步完善。著名的分布式计算项目 “Great Internet Mersenne Prime Search (GIMPS)” 使用此测试来寻找 Mersenne 素数（即同时为素数的 Mersenne 数）。截至本题撰写时，已知的最大 Mersenne 素数是 $2^{32\,382\,657} - 1$，由 Curtis Cooper 和 Steven Boone 于 2006 年 9 月 4 日发现。

该测试的步骤如下。设 $M_p = 2^p - 1$ 为待测的 Mersenne 数，其中 $p$ 为正整数（在实际应用中，只有当 $p$ 本身为大素数时，$M_p$ 的素性才有意义；若 $p$ 为合数，则 $M_p$ 也必为合数）。定义数列 $\{s_i\}$ 对所有 $i\ge0$ 如下：

$$s_0 = 4;\\ s_i = s_{i-1}^2 - 2,\quad \forall\, i>0. $$

当且仅当

$$s_{p-2}\equiv 0\pmod{M_p}$$

时，$M_p$ 为素数。数 $s_{p-2}\bmod M_p$ 即称为指数 $p$ 的 Lucas–Lehmer 余数。

你的任务是编写一个简单的 Lucas–Lehmer 测试实现。

输入

输入包含若干行，每行一个不超过 8192 的正整数（不一定是素数）。文件结尾（EOF）表示输入结束。

输出

对于每个输入的整数，输出它的 Lucas–Lehmer 余数的十六进制表示，使用数字 0–9 和小写字母 a–f，每个结果占一行。

---

59
61

64099e5fcbcaf36
0

来源

POJ Monthly–2007.08.05, frkstyc