Problem Description

Given a sequence $a$:

• When $n \le 2$, $a_n = n$.
• When $n > 2$ and $n$ is odd, $a_n = 2 \times a_{n-1}$.
• When $n > 2$ and $n$ is even, $a_n = a_{n-1} + r_{n-1}$.

Here, $r_{n-1} = \operatorname{mex}(|a_i - a_j|)(1 \le i \le j \le n - 1)$, and $\operatorname{mex}\left\{ S \right\}$ denotes the smallest non-negative integer that is not in the set $S$.

The first several terms of the sequence $a$ are:

$1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980$.

It can be proven that for any positive integer $x$, there exists a unique pair of integers $(p, q)$ such that $x = a_p - a_q$, which is defined as $\operatorname{repr}(x)$.

For example, $\operatorname{repr}(17) = (6, 3)$, and $\operatorname{repr}(18) = (16, 15)$.

Now there are $n$ queries. Each query gives a positive integer $x$. For each query, output $\operatorname{repr}(x)$.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain a positive integer $x$, representing a query.

Output Format

Output $n$ lines. Each line contains two positive integers $p, q$, answering each query in order.

2
17
18

6 3
16 15

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, and $1 \le x \le 10^9$.

Translated by ChatGPT 5