28811번 - Монетки 다국어

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

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

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

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

В первой строке содержится число $q$ --- количество тестов ($1 \le q \le 10^6$).

В $i$-й из следующий $q$ строк содержится число $n_i$ --- размер изначального прямоугольника с монетками ($1 \le n_i \le 10^6$).

Выведите $q$ строк, в $i$-й из которой должны находиться два числа $x_i$ и $y_i$ --- размеры нового прямоугольника прямоугольника ($x_i \le 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 \cdot 65$, периметр 70;
• $13 \cdot 25$, периметр 38.

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