Məsələlər
Сумма двух квадратов
Сумма двух квадратов
Как известно, любое простое число \textbf{p} вида \textbf{4k}+\textbf{1} представимо в виде суммы двух квадратов натуральных чисел, причем единственным способом. В данной задаче вам предлагается найти такое представление. Чтобы облегчить задачу, будут рассматриваться только простые числа вида \textbf{8k}+\textbf{5}.
\InputFile
В первой строке входного файла задано натуральное число \textbf{T} ≤ \textbf{1000}, количество простых чисел вида \textbf{8k}+\textbf{5}, которые вам надо представить в виде суммы двух квадратов натуральных чисел. В последующих \textbf{T} строках заданы сами эти числа. Гарантируется, что каждое из них является простым числом, дает остаток \textbf{5} при делении на \textbf{8} и не превосходит \textbf{10^18}.
\OutputFile
Для каждого простого числа \textbf{p} из входного файла выведите в отдельной строке через пробел пару натуральных чисел \textbf{x} и \textbf{y} такую, что \textbf{x} < \textbf{y} и \textbf{x^2}+\textbf{y^2}=\textbf{p}.
Giriş verilənləri #1
4 5 13 29 999999999999999989
Çıxış verilənləri #1
1 2 2 3 2 5 260483990 965478167