J. Antimatter
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A dark magic shop has received the newest numeric tape made of antimatter. The tape is infinite in one direction and consists of cells with non-negative integers written on them: the number $$$0$$$ is written at the finite end, then the numbers $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, and so on to infinity.

For his research, Svetozar urgently needs a contiguous segment $$$[L, R]$$$ of this tape, and not just any segment, but one such that the bitwise XOR of all its numbers equals a given magic number $$$A$$$.

Magical goods are not cheap, so he needs a suitable segment with the smallest possible $$$R$$$. You may find any valid value of $$$L$$$. Anyway, when buying, the tape still has to be cut up to $$$R$$$ inclusive.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The only line of a test case contains an integer $$$A$$$ ($$$0 \leq A \leq 10^{18}$$$).

Output

For each test case, print integers $$$L$$$ and $$$R$$$ ($$$0 \leq L \leq R \leq 10^{18}$$$) on a separate line: the bounds of a suitable segment. $$$R$$$ must be as small as possible. If there are several valid values of $$$L$$$ for the smallest $$$R$$$, print any.

It can be shown that under the given constraints at least one solution exists.

Example
Input
8
0
1
2
3
4
5
6
7
Output
0 0
1 1
2 2
1 2
1 4
2 4
6 6
3 4
Note

Recall that the bitwise XOR of two non-negative integers $$$x$$$ and $$$y$$$ is a non-negative integer $$$z$$$ whose binary representation has a bit equal to $$$1$$$ if the corresponding bits of $$$x$$$ and $$$y$$$ differ, and $$$0$$$ if they coincide.