E. Freshman's Dream
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Everyone knows that (a + b)^n is never equal to a^n + b^n for positive integers $$$a, b$$$ and $$$n$$$ if $$$n \ge 2$$$. Or is it? Look again.

Given an integer $$$n \ge 2$$$, you have to find positive integers $$$a$$$ and $$$b$$$ such that (a + b)^n is equal to a^n + b^n, where every symbol is interpreted as it is in C++, including operator precedence. In other words, you have to find $$$a$$$ and $$$b$$$ such that $$$$$$ (a + b) \oplus n = a \oplus (n + b) \oplus n $$$$$$ holds, where $$$\oplus$$$ is the bitwise XOR operation.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. $$$t$$$ test cases follow.

Each test case consists of one integer $$$n$$$ ($$$2 \le n \lt 2^{60}$$$).

Output

For each test case, print the answer on a separate line as follows.

  • If there is no solution, print $$$-1$$$.
  • Otherwise, print positive integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \lt 2^{60}$$$) such that the equation in the problem statement holds. Under the constraints of the problem, it can be proven that if there is a solution, then there is also a solution with $$$a, b \lt 2^{60}$$$. If there are multiple solutions, you can print any one of them.
Example
Input
5
2
3
6
10
18
Output
1 1
-1
3 5
7 3
11 39