F. Resli-utiful Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Resli is never satisfied with only one problem, so here is another problem prepared for you by Resli.

We define a pair of integers $$$(a, b)$$$ to be a Resli-utiful Pair if it holds that:

  • $$$a^b \equiv 1 \bmod N$$$.
  • $$$a^b$$$ is a perfect square.
  • $$$2 \le a \le 2 \cdot 10^9$$$.
  • $$$2 \le b \le 2 \cdot 10^9$$$.

A perfect square is a positive integer that is obtained by multiplying an integer by itself, i.e. $$$4$$$ is a perfect square because it is obtained from $$$2 \times 2$$$, but $$$6$$$ is not.

Your task is easy. Given $$$N$$$, find any Resli-utiful Pair. It's guaranteed that the answer always exist.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of testcases.

The only line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 10^9)$$$ — the integer $$$N$$$.

Output

For each testcase, print in a separate line two space-separated integers $$$a$$$ and $$$b$$$ that are a Resli-utiful Pair.

Example
Input
1
2
Output
5 2