Монетки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

В первой строке содержится число q — количество тестов (1 ≤ q ≤ 106).

В i-й из следующий q строк содержится число ni — размер изначального прямоугольника с монетками (1 ≤ ni ≤ 106).

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

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

Пример

Входные данные
6
1
2
3
4
5
18
Выходные данные
-1
-1
2 5
-1
2 13
5 65

Примечание

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

32 + 1 = 10 и 52 + 1 = 26 монеток уложить в прямоугольник единственным способом, а 182 + 1 = 325 монеток можно уложить двумя способами:

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