Description

Source Problem: POI XXVII - I etap (Najmniejsza wspólna wielokrotność)

Byteasar is studying for a maths test which will focus on determining the least common multiple. Recall that the least common multiple (lcm) of integers $a_1, \ldots, a_k$ is the least positive integer d such that each of $a_1, \ldots, a_k$ is its divisor. For example, $\mathrm{lcm}(8, 12) = 24$, whereas $\mathrm{lcm}(2, 3, 4) = 12$.

Byteasar quickly mastered the standard exercises, and found the subject so amusing that he started inventing tasks of his own. Let us find out if you are able to solve one of those.

For a given positive integer $M$ you are to return an interval of positive integers $[a, b]$ such that the least common multiple of all the integers in it is exactly $M$. The interval $[a, b]$ has to contain at least two positive integers.

To thoroughly test your skills, Byteasar will ask you (or rather your program) multiple queries.

Input Format

In the first input line there is a single integer $z$ which specifies the number of Byteasar’s queries. The next $z$ lines specify the queries, one per line. Each query is specified by a single integer $M$.

Output Format

Your program should print exactly $z$ lines to the standard output. The $i$-th of these should contain the answer to the $i$-th Byteasar’s query. An answer to a query consists of two positive integers $a$ and $b$, separated by a single space, which stand for the interval of integers $[a, b]$.

If no interval satisfies the desired property, the single word NIE (Polish for no) should be printed instead of any numbers.

If there is more than one answer, report the one with minimum $a$, breaking ties (if any) in favor of smaller $b$.

3
12
504
17

1 4
6 9
NIE

Additional Samples

See files nww/nww*.in and nww/nww*.out for additional samples.

Additional Sample 1: five $M$ values: $5$, $6$, $7$, $8$, and $9$, Additional Sample 2: single $M$ value: $1~000~000$, Additional Sample 3: single $M$ value: $99~999~990~000~000$, Additional Sample 4: $z = 10~000$, the values of $M$ alternate between $500~001~500~001~000~001$ and $500~001~500~001~000~000$.

Constraints