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

$$10 = 2 \cdot 5$$ $$= 5 \cdot 2$$

$$20 = 2 \cdot 2 \cdot 5$$ $$= 2 \cdot 5 \cdot 2$$ $$= 5 \cdot 2 \cdot 2$$

设 $f(k)$ 为 $k$ 的素因子所有不同排列方式的数量。因此 $f(10) = 2$ 且 $f(20) = 3$。

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

输入格式

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

输出格式

对于每个测试用例，输出其对应的 $n$ 以及满足 $f(k) = n$ 的最小整数 $k > 1$。输入数据保证 $k < 2^{63}$。

样例

样例输入 1

1
2
3
105

样例输出 1

1 2
2 6
3 12
105 720