Монетки#11037

Монетки

2 секунди

128 мегабайтів

Середня

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

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

Прямокутник вміщує в себе всі монетки і не містить порожніх місць, тобто $x \times y = n^{2} + 1$ x \times y = n^2 + 1;
Периметр прямокутника максимально можливий;
Кожна сторона прямокутника повинна мати довжину хоча б $2$ .

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

Вхідні дані

У першому рядку міститься кількість тестів $q$ ( $1 \leq q \leq 1 0^{6}$ 1 \leq q \leq 10^6). В $i$ -му з наступних $q$ рядків міститься розмір $n_{i}$ n_i ( $1 \leq n_{i} \leq 1 0^{6}$ 1 \leq n_i \leq 10^6) початкового прямокутника з монетками.

Вихідні дані

Виведіть $q$ рядків, в $i$ -му з яких повинні знаходитися два числа $x_{i}$ x_i і $y_{i}$ y_i ( $x_{i} \leq y_{i}$ x_i \leq y_i) - розміри нового прямокутника або $- 1$ , якщо прямокутника, що задовольняє умовам задачі, не існує.

Приклади

Приклад 1

Примітка

У тестовому прикладі числа $1^{2} + 1 = 2$ 1^2 + 1 = 2, $2^{2} + 1 = 5$ 2^2 + 1 = 5 і $4^{2} + 1 = 17$ 4^2 + 1 = 17 - прості, і таку кількість монеток не можна укласти в прямокутник, що задовольняє умовам задачі.

$3^{2} + 1 = 10$ 3^2 + 1 = 10 і $5^{2} + 1 = 26$ 5^2 + 1 = 26 монеток укласти в прямокутник єдиним способом, а $1 8^{2} + 1 = 325$ 18^2 + 1 = 325 монеток можна укласти двома способами:

$5 \times 65$ 5 \times 65, периметр $70$ ;
$13 \times 25$ 13 \times 25, периметр $38$ .

У першому випадку периметр більший, тому це і буде відповіддю.