ENUMRTNL - Enumeration of rationals

no tags 

It is well known that rational numbers form a countable set. Hence the set of rational numbers in the open interval (0,1) also form a countable set.

Here we enumerate the rationals in (0,1) in the following fashion. First, every rational is expressed in the lowest terms : ie, as p/q where p and q are positive integers with no common factor other than one. Then we sort the fractions in the ascending order of p+q. In case of a tie, the smaller fraction comes first.

The first few terms in this enumeration are 1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5...

Given a natural number N, find the numerator and denominator of the Nth term in the enumeration.

Input

The first line of the input contains T (≤ 1000), the number of test cases. This is followed by T lines, each containing an integer N (≤ 1011).

Output

For each value of N, output separated by space the numerator and denominator (in lowest terms) of the Nth fraction in the enumeration

Example

Input:
2
3
6

Output:
1 4
1 6

hide comments
Ouditchya Sinha: 2013-07-22 14:04:42

Very good problem. Learnt a lot from it. Maths is amazing! :)

Raziman T V: 2011-02-22 18:23:04

I increased the time limit to 5s and your solution has got accepted

David: 2011-02-22 18:21:02

Thanks for the assistance with the time limit.

Last edit: 2011-02-23 17:58:02

Added by:Raziman T V
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOPC2011