D is a given positive integer, consider the equation :
X² = D×Y² + 1, with X and Y positive integers.
Find the minimum numbers (X,Y) within all solutions.
Sometimes it's possible, sometimes not!

Examples :
If D=2, 3² = 2×2² + 1, so X=3 and Y=2.
If D=3, 2² = 3×1² + 1, so X=2 and Y=1.
If D=4, it's impossible!

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there is one integer D.

Output

For each test case, if possible print X and Y the answer of the problem for D, else "-1".

Example

Input:
3
2
3
4

Output:
3 2
2 1
-1

Constraints

T <= 1000
1 < D <= 10^7, the numbers D were randomly chosen. (but XerK modified one of them!)
190 bytes of sub-optimal python code can get AC in less than 2.5 seconds, there's many rooms to make faster code.
If you have TLE, you should first consider EQU2 first.

Edit(2017-02-11, after compiler updates) : New TL at 1.5s. The Python awaited solution ends under 0.8s, pike or java around 1.4s. Some old AC might not keep their AC : here it's mid-pelling. The 'mid' is to be kept in consideration.