Enumeration of rationals

All submissions for this problem are available.
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(≤10^{11}).
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
Author:  razimantv 
Tags  razimantv 
Date Added:  6022011 
Time Limit:  0.373461 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO, NODEJS, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 