Coins

When no one plays the machine with its game and Ralph gets bored, he goes out for a walk and collect coins. For all the time he has already collected as many as n^2 pieces. Despite his appearance, he also likes neatness, so he put them all in a square n * n, one coin per cell, so that there was no free space in the square.

However, Felix unexpectedly came to visit Ralph and brought another coin. Our hero was extremely happy with such attention and surprise, but he had absolutely no idea where to put it now. So he decided to change the place to store the coins and put all n^2 + 1 coins in another rectangle. However, not everything is so simple, because Ralph is not only neat, but also picky. Namely, he wants the new rectangle x * y, where his coins are stored, to satisfy the following conditions:

• The rectangle contains all the coins and does not contain empty spaces, i.e. x * y = n^2 + 1;

• The perimeter of the rectangle is as maximum as possible;

• Each side of the rectangle must be at least 2 long.

Based on the value of n, Ralph wants to find the treasured numbers x and y, and as soon as possible - the production of the rectangle needs to start now. Help him!

Input

The first line contains the number of tests q (1 ≤ q ≤ 10^6). The i-th of the next q lines contains the size n[i] (1 ≤ n[i] ≤ 10^6) of the original coin rectangle.

Output

Print q lines, i-th of which should contain two numbers x[i] and y[i] (x[i] ≤ y[i]) - the dimensions of the new rectangle or -1 if the rectangle that satisfies the conditions of the problem does not exist.

Examples

Note

In the test example, the numbers 1^2 + 1 = 2, 2^2 + 1 = 5 and 4^2 + *1 * = 17 are prime, and such a number of coins cannot be placed in a rectangle that satisfies the conditions of the problem.

3^2 + 1 = 10 and 5^2 + 1 = 26 put the coins into the rectangle in the only way, and 18^2 + * 1* = 325 coins can be put in two ways:

• 5 * 65, perimeter 70;

• 13 * 25, perimeter 38.

In the first case, the perimeter is bigger, so this is the answer.