Description

算术基本定理指出，每个大于 $1$ 的整数都可以唯一表示为一个或多个素数的乘积。虽然表示是唯一的，但素数因子的排列可能有多种。例如：

• $10=2\times 5=5\times 2$；
• $20=2\times 2\times 5=2\times 5\times 2=5\times 2\times 2$；

令 $f(k)$ 为 $k$ 的素数因子不同排列的数量。因此，$f(10) = 2$ 且 $f(20) = 3$。

给定一个正整数 $n$，总是至少存在一个数字 $k$ 使得 $f(k) = n$。我们想知道最小的这样的 $k$。

Input Format

输入包含最多 $1 000$ 个测试用例，每个测试用例占一行。每个测试用例是一个正整数 $n < 2^{63}$。

Output Format

对于每个测试用例，输出其数字 $n$ 以及最小的 $k > 1$ 使得 $f(k) = n$。输入中的数字选择使得 $k < 2^{63}$。

翻译来自于：ChatGPT。

1
2
3
105

1 2
2 6
3 12
105 720