Sum of two squares#650
It is well known that any prime number of the form 4k+1 can be expressed as the sum of the squares of two natural numbers. Moreover, this representation is unique. In this problem, you are required to find such a representation. To simplify the task, only prime numbers of the form 8k+5 will be considered.
The first line contains a natural number (1 \leq T \leq 1000), the number of primes of the form 8k+5 to be considered. The following lines contain these numbers. It is guaranteed that each of them is a prime, leaves a remainder of when divided by , and does not exceed 10^{18}.
For each prime from the input, output on a separate line a pair of natural numbers and such that x < y and x^2 + y^2 = p.
Example 1