Sum of two squares

It is well known that any prime number p of the form 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 8k+5 will be only considered.

Input

The first line contains a natural number T ≤ 1000, the number of primes of the form 8k+5, which will be considered. In following T lines these numbers are given. It is provided that each of them is prime, has remainder 5 when divided by 8, and does not exceed 10^18.

Output

For each prime p from input file you should output in a separate line the pair of numbers x and y such that x < y and x^2+y^2=p.

Examples