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

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

Вхідні дані

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

Вихідні дані

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

Приклади