题目描述

小明准备进行考试。

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

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

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

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

输入格式

在文件 gcd.in 中读入。

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

输出格式

在文件 gcd.out 中输出。

$z$ 行每行两个整数 $a,b$ 代表一个询问的答案。

如果有多组解：

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

如果无解，则输出 NIE。

输入输出样例 #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（20 pts）：$z \le 10$，$M \le 1000$。
• Subtask 2（80 pts）：$1 \le z\le 10^4$，$1 \le M \le 10^{18}$。