Unique Representation by a Special Sequence

We define a sequence \(a\) as follows:

- For \(n \le 2\), \(a_n = n\).

- For \(n > 2\):

• If \(n\) is odd, then \(a_n = 2 \times a_{n-1}\).
• If \(n\) is even, then \(a_n = a_{n-1} + r_{n-1}\), where

\[ r_{n-1} = \operatorname{mex}\Big(\{|a_i-a_j| : 1 \le i \le j \le n-1\}\Big) \]

The function \(\operatorname{mex}(S)\) returns the smallest nonnegative integer that is not in \(S\). For example, the first several terms of \(a\) are given by:

[ 1,; 2,; 4,; 8,; 16,; 21,; 42,; 51,; 102,; 112,; 224,; 235,; 470,; 486,; 972,; 990,; 1980, \dots ]

It can be proven that for any positive integer \(x\), there exists a unique pair of positive integers \((p,q)\) such that

[ x = a_p - a_q, ]

and we denote this pair by (\operatorname{repr}(x) = (p,q)). For instance, (\operatorname{repr}(17) = (6,3)) because (a_6 - a_3 = 21-4 = 17), and (\operatorname{repr}(18) = (16,15)) because (a_{16} - a_{15} = 990-972 = 18>.

Your task is to answer \(n\) queries. In each query, given a positive integer \(x\), output the unique pair \((p,q)\) such that \(x = a_p - a_q\).

inputFormat

The first line contains a single integer \(T\) (\(1 \le T\)) representing the number of queries.

Each of the following \(T\) lines contains one positive integer \(x\).

outputFormat

For each query, output two integers \(p\) and \(q\) (separated by a space) on a separate line such that \(x = a_p - a_q\).

sample

5
1
5
7
17
18

2 1
6 5
4 1
6 3
16 15

</p>