After completing the Death Star, the Galactic Empire secretly began constructing Death Star II with the aim of consolidating power and creating a more powerful deterrent. After the Death Star was destroyed due to a serious design flaw, Palpatine not only had to expedite the construction of Death Star II, but he also set higher demands for the engineers building it. Not only must they be skilled builders, but they also need to be proficient in mathematics and programming. Each engineer applying will be asked the following problem:

• Given an integer ~n~ (~1 \leq n < 2^{30}~), find two positive integers ~x, y~ (~1 \leq x, y < 2^{60}~) such that ~x \oplus y = gcd(x, y) = n~.

Although you are a novice engineer, you have an advantage over other candidates with your programming experience. Will you be able to pass this test?

Input

Each test contains multiple test cases.The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~).

The only line of each test case contains an integer ~n~ (~1 \leq n < 2^{30}~).

Output

For each test case, print a single line containing two integers ~x, y~ (~1 \leq x, y < 2^{60}~) that satisfy the condition ~x \oplus y = gcd(x, y) = n~.

Sample Input 1

2
2
5

Sample Output 1

12 14
10 15