Problem Background

Byteasar is preparing for his math exam.

Problem Description

His teacher mentioned that the exam would include questions about the least common multiple (LCM), so he found a problem to practice.

Given an integer \( M \), find an interval \([a, b]\) such that \( M \) is the LCM of all numbers in this interval.

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

Because Byteasar loves asking questions, he will ask you \( z \) sets of questions.

Input Format

The first line contains an integer \( z \) representing the number of queries.
The next \( z \) lines each contain an integer \( M \) representing a query.

Output Format

Output \( z \) lines, each containing two integers \( a \) and \( b \) representing the answer to a 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 \).

Sample Input and Output

Sample Input #1

3
12
504
17

Sample Output #1

1 4
6 9
NIE

Sample Input #2

5
5
6
7
8
9

Sample Output #2

NIE
1 3
NIE
NIE
NIE

Sample Input #3

1
1000000

Sample Output #3

NIE

Sample Input #4

1
99999990000000

Sample Output #4

9999999 10000000

Notes

Sample Explanation

For the first set of data in Sample 1, \( 12 \) is the LCM of the interval \([1, 4]\).

Additional samples can be found in the attached files sample.in and sample.out.

Data Size and Constraints

This problem uses subtask testing.

• 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 restrictions.

For 100% of the data, \( 1 \le z \le 10^4 \), \( 1 \le M \le 10^{18} \).

Notes

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

见题面 Input 部分

见题面 Output 部分