You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最小公倍数区间

题目描述

给定一个整数 $M$，求一个区间 $[a,b]$ 使得 $M$ 为这个区间所有数的最小公倍数，要求$a<b$。 $z$ 次询问。如果不存在这样的区间就输出NIE。

输入格式

第一行一个整数 $z$ 代表询问个数。

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

输出格式

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

如果有多组解：

输出 $a$ 最小的

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

样例 #1

样例输入 #1

3
12
504
17

样例输出 #1

1 4
6 9
NIE

样例 #2

样例输入 #2

5
9
8
7
6
5

样例输出 #2

NIE
NIE
NIE
1 3
NIE

样例 #3

样例输入 #3

1
99999990000000

样例输出 #3

9999999 10000000

提示

样例解释1：

对样例1的第一个数$12$，区间$[1,4],[2,4],[3,4]$都满足条件，因此输出1 4。

数据范围

对所有数据满足$1 \le z\le 10^4$，$1 \le M \le 10^{18}$。

特殊性质：输入的所有数都是质数