Задачі
Сума двох квадратів
Сума двох квадратів
Як відомо, довільне просте число p виду 4k+1 можна подати у вигляді суми двох квадратів натуральних чисел, причому єдиним чином. У даній задачі вам пропонується знайти таке подання. Щоб полегшити ваше завдання, будуть розглядатись лише прості числа виду 8k+5.
Вхідні дані
У першому рядку вхідного файлу задано натуральне число T ≤ 1000, кількість простих чисел виду 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