AT_arc191_c.[ARC191C] A^n - 1

给定范围在 $1$ 至 $10^9$ 之间的正整数 $N$。

请找出一个满足以下两个条件的正整数对 $(A, M)$。可以证明在约束条件下这样的正整数对必然存在：

• $A$ 和 $M$ 均为 $1$ 至 $10^{18}$ 之间的正整数。
• 存在某个正整数 $n$ 使得 $A^n - 1$ 是 $M$ 的倍数，且满足此条件的最小 $n$ 恰好为 $N$。

给定 $T$ 个测试用例，请分别计算每个用例的答案。

输入通过标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

其中，$\text{case}_i$ 表示第 $i$ 个测试用例。每个测试用例的格式为：

$N$

对于每个测试用例，输出满足条件的正整数对 $(A, M)$，格式如下：

$A$ $M$

若存在多个符合条件的解，输出任意一个均可视为正确。

约束条件

• $1 \leq T \leq 10^4$
• $1 \leq N \leq 10^9$
• 输入均为整数

样例解释 1

以第一个测试用例 $\text{case}_1$ 为例：
若选择 $(A, M) = (2, 7)$，则：

• 当 $n = 1$ 时：$2^1 - 1 = 1$，不是 $7$ 的倍数。
• 当 $n = 2$ 时：$2^2 - 1 = 3$，不是 $7$ 的倍数。
• 当 $n = 3$ 时：$2^3 - 1 = 7$，是 $7$ 的倍数。

此时满足条件的最小 $n$ 为 $3$，因此输出 $(2, 7)$ 是正确的。其他符合条件的解例如 $(100, 777)$ 也可接受。

翻译由 DeepSeek R1 完成