C. XOR LCM
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$c(1 \le c \le 10^7)$$$.

You need to find two positive integers $$$a$$$ and $$$b$$$ such that:

  • $$$1 \le a, b \le 10^{17}$$$
  • $$$ (a \oplus c) + (b \oplus c) = lcm(a, c) + lcm(b, c)$$$, where $$$\oplus$$$ is the bitwise XOR operator and $$$lcm(x, y)$$$ is the lowest common multiple of $$$x$$$ and $$$y$$$.

It can be proven that it is always possible to find $$$a$$$ and $$$b$$$ for the given constraints.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains an integer $$$c$$$ ($$$1 \le c \le 10^7$$$).

Output

For each test case, output two integers $$$a$$$ and $$$b$$$.

Example
Input
3
1
2
7
Output
88 71
80 62
1 35