It is well known that any prime number \textbf{p} of the form \textbf{4k+1} can be presented as the sum of squares of two natural numbers. Moreover, this presentation is unique. In this task you are proposed to find required presentation. To simplify the task prime numbers of the form \textbf{8k+5} will be only considered. \InputFile The first line contains a natural number \textbf{T} ≤ \textbf{1000}, the number of primes of the form \textbf{8k+5}, which will be considered. In following \textbf{T} lines these numbers are given. It is provided that each of them is prime, has remainder \textbf{5} when divided by \textbf{8}, and does not exceed \textbf{10^18}. \OutputFile For each prime \textbf{p} from input file you should output in a separate line the pair of numbers \textbf{x} and \textbf{y} such that \textbf{x} < \textbf{y} and \textbf{x^2}+\textbf{y^2}=\textbf{p}.