题目背景

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

题目描述

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

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

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

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

输入格式

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

输出格式

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

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

输入输出样例 #1

输入 #1

3
12
504
17

输出 #1

1 4
6 9
NIE

输入输出样例 #2

输入 #2

5
5
6
7
8
9

输出 #2

NIE
1 3
NIE
NIE
NIE

输入输出样例 #3

输入 #3

1
1000000

输出 #3

NIE

输入输出样例 #4

输入 #4

1
99999990000000

输出 #4

9999999 10000000

说明/提示

样例说明

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

数据规模与约定

本题采用捆绑测试。

• 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}$。