L. Squares in a Square
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

An integer $$$x$$$ is called square if there exists an integer $$$y$$$ such that $$$y^2 = x$$$. For example, $$$25, 36, 100$$$ are square integers; $$$5, 10, 32$$$ are not.

Consider a matrix consisting of $$$n$$$ rows and $$$n$$$ columns. It is filled with integers from $$$1$$$ to $$$n^2$$$ as follows:

  • the first row contains integers $$$1, 2, 3, \dots, n$$$ from left to right;
  • the second row contains integers $$$n+1, n+2, n+3, \dots, 2n$$$ from left to right;
  • and so on.

For example, the matrix for $$$n=5$$$ is as follows:

$$$$$$ \left(\begin{array}{ccccc} 1&2&3&4&5\\ 6&7&8&9&10\\ 11&12&13&14&15\\ 16&17&18&19&20\\ 21&22&23&24&25 \end{array}\right). $$$$$$

Your task is to find any two distinct square integers in the last column of this matrix.

Input

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

Each test case consists of one line containing one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^9$$$).

Output

For each test case, print two square integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n^2$$$; $$$x \ne y$$$) that both belong to the last column of the matrix. If there are multiple answers, print any of them. If there is no answer, print 0 0 instead.

Example
Input
3
5
100
998244353
Output
0 0
100 10000
0 0