The Main Character

Input

First line consists of an integer $t$ (1 \le t \le 10^5), the number of testcases.

The next $t$ lines each contain an integer $n$ (1 \le n \le 10^{18}).

Output

For each test case output two integers $(x,y)$ as an answer , If multiple answers exist print any.

Examples

Note

In the first testcase, There are only two pairs ($x$,$y$) that satisfy the first two conditions, ($2$,$5$),($5$,$2$), and since both have the same x+y value, you can output any.

In the second testcase, Since $n$ doesn't end with $0$, we can just choose one of the two pairs ($1$,$6741$),($6741$,$1$), because they achieve the maximum value of x+y out of all the other pairs.

Scoring

• Subtask $1$ ($15$ points): $n$ is odd

• Subtask $2$ ($15$ points): (1 \le n \le 500)

• Subtask $3$ ($20$ points): (1 \le n \le 10^5)

• Subtask $4$ ($50$ points): no additional constraints