Mr. Abul is a big fan of prime numbers. As a fan of prime numbers, he wants to know whether a prime number P can be expressed as difference of two squared numbers or not.

In other words you have to calculate two natural numbers X and Y where P = X^2 - Y^2

For example, prime number P = 5 can be expressed as 3^2 - 2^2 = 9 - 4 = 5, here X = 3 and Y = 2.

Input

Input starts with an integer T ≤ 100, denoting the number of test cases.

Each case contains an integer N (2 ≤ N ≤ 10^18) denoting a prime number.

Output

For each case of input, print X and Y separated by a space if it is possible to express as difference of two squared numbers. Otherwise, print -1.

Example

Input:
3
2
3
5

Output:
-1
2 1
3 2