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¹¹).

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