Монетки

Когда в автомат с его игрой никто не играет и Ральфу становится скучно, он выходить прогуляться и пособирать монетки. За все время он собрал их уже целых n^2 штук. Несмотря на свой внешний вид, он также любит аккуратность, поэтому уложил их все в квадрат n * n, по одной монетке в ячейку, так, что свободного места в квадрате не осталось.

Однако, неожиданно к Ральфу в гости пришел Феликс и принес еще одну монетку. Наш герой был безумно рад такому вниманию и сюрпризу, но абсолютно не имел понятия, куда ее теперь положить. Поэтому он решил поменять место для хранения монеток и положить все n^2 + 1 монетку в другой прямоугольник. Однако, не все так просто, ведь Ральф не только аккуратен, но и придирчив. А именно, он хочет, чтобы для нового прямоугольника x * y - места хранения его монеток - выполнялись следующие условия:

• Прямоугольник вмещает в себя все монетки и не содержит пустых мест, то есть x * y = n^2 + 1;

• Периметр прямоугольника максимально возможный;

• Каждая сторона прямоугольника должна иметь длину хотя бы 2.

По данному n Ральф хочет найти заветные числа x и y, и как можно быстрее - изготовлениепрямоугольника нужно начинать уже сейчас. Помогите ему!

Входные данные

В первой строке содержится количество тестов q (1 ≤ q ≤ 10^6). В i-й из следующий q строк содержится размер n[i] (1 ≤ n[i] ≤ 10^6) изначального прямоугольника с монетками.

Выходные данные

Выведите q строк, в i-й из которой должны находиться два числа x[i] и y[i] (x[i] ≤ y[i]) - размеры нового прямоугольника или -1, если прямоугольника, удовлетворяющего условиям задачи, не существует.

Примеры

Примечание

В тестовом примере числа 1^2 + 1 = 2, 2^2 + 1 = 5 и 4^2 + 1 = 17 - простые, и такое количество монеток нельзя уложить в прямоугольник, удовлетворяющий условиям задачи.

3^2 + 1 = 10 и 5^2 + 1 = 26 монеток уложить в прямоугольник единственным способом, а 18^2 + 1 = 325 монеток можно уложить двумя способами:

• 5 * 65, периметр 70;

• 13 * 25, периметр 38.

В первом случае периметр больше, поэтому это и будет ответом.