Как известно, любое простое число p вида 4k+1 представимо в виде суммы двух квадратов натуральных чисел, причем единственным способом. В данной задаче вам предлагается найти такое представление. Чтобы облегчить задачу, будут рассматриваться только простые числа вида 8k+5.
В первой строке входного файла задано натуральное число T ≤ 1000, количество простых чисел вида 8k+5, которые вам надо представить в виде суммы двух квадратов натуральных чисел. В последующих T строках заданы сами эти числа. Гарантируется, что каждое из них является простым числом, дает остаток 5 при делении на 8 и не превосходит 10^18.
Для каждого простого числа p из входного файла выведите в отдельной строке через пробел пару натуральных чисел x и y такую, что x < y и x^2+y^2=p.