Background

Byteasar is preparing for his math exam.

Problem Description

The teacher told him that the exam would include problems about the least common multiple $\rm lcm$, so he found a problem to practice.

Given an integer $M$, find an interval $[a,b]$ such that $M$ is the least common multiple of all integers in this interval.

Since you are very strong, while Byteasar was solving this problem, he also wanted to ask you for the answer to this problem.

Because Byteasar loves asking questions, he will ask you $z$ queries.

Input Format

The first line contains an integer $z$, the number of queries.
Then follow $z$ lines, each containing an integer $M$ for one query.

Output Format

Output $z$ lines, each containing two integers $a,b$, the answer for one query.

If there are multiple solutions:

• Output the one with the smallest $a$.
• If there are still multiple solutions, output the one with the smallest $b$.

If there is no solution, output NIE.

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

Hint

Sample Explanation

For the first query in sample $1$, $12$ is the least common multiple of the interval $[1,4]$.

Another additional sample is provided in the attached files sample.in and sample.out.

Constraints

This problem uses bundled testdata.

• 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): no special limits.

For $100\%$ of the testdata, $1 \le z \le 10^4$, $1 \le M \le 10^{18}$.

Note

Translated from POI 2019 A Najmniejsza wspólna wielokrotność.

Translated by ChatGPT 5