SP8334 ENUMRTNL - Enumeration of rationals

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.

The first line of the input contains T (

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