Least Common Multiple Interval

Given an integer \(M\), find an interval \([a,b]\) of consecutive integers such that the least common multiple (\(\mathrm{lcm}\)) of all numbers in the interval equals \(M\). Note that for any integer \(M\), the trivial interval \([M, M]\) always satisfies \(\mathrm{lcm}(M)=M\).

Byteasar has solved this problem, and now he asks you to answer \(z\) queries.

inputFormat

The first line contains an integer \(z\) representing the number of queries. Each of the following \(z\) lines contains one integer \(M\).

outputFormat

For each query, output two space-separated integers \(a\) and \(b\) such that \([a,b]\) is an interval with \(\mathrm{lcm}(a, a+1, \ldots, b)=M\).

sample

3
1
6
12

1 1
6 6
12 12