eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сума двох квадратів

Сума двох квадратів

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Як відомо, довільне просте число p виду 4k+1 можна подати у вигляді суми двох квадратів натуральних чисел, причому єдиним чином. У даній задачі вам пропонується знайти таке подання. Щоб полегшити ваше завдання, будуть розглядатись лише прості числа виду 8k+5.

Вхідні дані

У першому рядку вхідного файлу задано натуральне число T1000, кількість простих чисел виду 8k+5, які вам потрібно подати у вигляді суми двох квадратів натуральних чисел. У наступних T рядках задані самі ці числа. Гарантується, що кожне з них є простим числом, дає остачу 5 при діленні на 8 і не перевищує 10^18.

Вихідні дані

Для кожного простого числа p з вхідного файлу виведіть в окремому рядку через пропуск пару натуральних чисел x та y таку, що x < y і x^2+y^2=p.

Приклад

Вхідні дані #1
4
5
13
29
999999999999999989
Вихідні дані #1
1 2
2 3
2 5
260483990 965478167
Автор А.Лунев
Джерело Зимние сборы в Харькове 2010 День 1