题目背景

Byteasar 正在准备他的数学考试。

题目描述

老师跟他说考试题目中有关于最小公倍数 $\rm lcm$ 的题目，于是他找到了一道题练练手。

给定一个整数 $M$，求一个区间 $[a,b]$ 使得 $M$ 为这个区间所有数的最小公倍数。

因为您很强，所以 Byteasar 在解出来这道题的同时也想问问您这题的答案。

因为 Byteasar 非常爱问问题，所以他要问您 $z$ 组问题。

输入格式

第一行一个整数 $z$ 代表询问个数。
接下来 $z$ 行每行一个整数 $M$ 代表一个询问。

输出格式

$z$ 行每行两个整数 $a,b$ 代表一个询问的答案。
如果有多组解：

• 输出 $a$ 最小的
• 如果还有多组解输出 $b$ 最小的

3
12
504
17

1 4
6 9
NIE

5
5
6
7
8
9

NIE
1 3
NIE
NIE
NIE

1
1000000

NIE

1
99999990000000

9999999 10000000

提示

样例说明

对于样例 $1$ 的第一组数据，$12$ 为区间 $[1,4]$ 的最小公倍数。

另一组附加样例见附加文件的 sample.in 和 sample.out。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（18 pts）：$z \le 10$，$M \le 1000$。
• Subtask 2（20 pts）：$z\le 100$，$M \le 10^9$。
• Subtask 3（20 pts）：$z \le 100$，$M \le 10^{18}$。
• Subtask 4（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le z\le 10^4$，$1 \le M \le 10^{18}$。

说明

翻译自 POI 2019 A Najmniejsza wspólna wielokrotność。