P6659 [POI 2019/2020 R1] Najmniejsza wspólna wielokrotność / Least Common Multiple

Byteasar is preparing for his math exam.

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.

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

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`.

#### 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](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) A [Najmniejsza wspólna wielokrotność](https://sio2.mimuw.edu.pl/c/oi27-1/p/nww/). Translated by ChatGPT 5