P6659 [POI 2019/2020 R1] Najmniejsza wspólna wielokrotność / 最小公倍数

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

老师跟他说考试题目中有关于最小公倍数 $\rm lcm$ 的题目，于是他找到了一道题练练手。 给定一个整数 $M$，求一个区间 $[a,b]$ 使得 $M$ 为这个区间所有数的最小公倍数。 因为您很强，所以 Byteasar 在解出来这道题的同时也想问问您这题的答案。 因为 Byteasar 非常爱问问题，所以他要问您 $z$ 组问题。

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

$z$ 行每行两个整数 $a,b$ 代表一个询问的答案。 如果有多组解： - 输出 $a$ 最小的。 - 如果还有多组解，输出 $b$ 最小的。 如果无解，则输出 `NIE`。

#### 样例说明 对于样例 $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](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) A [Najmniejsza wspólna wielokrotność](https://sio2.mimuw.edu.pl/c/oi27-1/p/nww/)。