Problem Statement

You are given a positive integer $N$ between $1$ and $10^9$, inclusive.

Find one pair of positive integers $(A, M)$ satisfying the following conditions. It can be proved that such a pair of integers always exists under the constraints.

• Both $A$ and $M$ are positive integers between $1$ and $10^{18}$, inclusive.
• There exists a positive integer $n$ such that $A^n - 1$ is a multiple of $M$, and the smallest such $n$ is $N$.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 10^4$
• $1 \le N \le 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Here, $\text{case}_i$ denotes the $i$-th test case. Each test case is given in the following format:

N

Output

For each test case, print a pair of positive integers $(A, M)$ in the following format:

A M

If there are multiple valid solutions, any one of them is considered correct.