我们定义一个无限实数序列 $a_1, a_2, a_3, \dots$ 如下：

$$ a_n = \begin{cases} n & \text{for } n \le 2 \\ 2 \cdot a_{n-1} & \text{for odd } n > 2 \\ a_{n-1} + r_{n-1} & \text{for even } n > 2 \end{cases} $$

其中 $r_{n-1}$ 是不能表示为集合 $\{a_1, a_2, \dots, a_{n-1}\}$ 中两个不同元素之差的最小正整数。

因此，该序列的初始元素为： $1, 2, 4, 8, 16, 21, 42, 51, 102, 112, 224, 235, 470, 486, 972, 990, 1980, \dots$

例如，为了确定 $a_6$，我们确定数字 $1, 2, 3, 4$ 均可表示为初始元素 $1, 2, 4, 8, 16$ 中某两个元素之差，而 $5$ 不能。因此，$a_6 = a_5 + 5 = 21$。

已知对于每个正整数 $x$，存在唯一的下标对 $(p, q)$ 使得 $x = a_p - a_q$。我们将这样的下标对记为 $repr(x)$。例如，$repr(17) = (6, 3)$ 且 $repr(18) = (16, 15)$。你的任务是对于给定的 $x$ 确定 $repr(x)$。

输入格式

标准输入的第一行包含一个整数 $n$，表示查询的数量。接下来的 $n$ 行，每行包含一个正整数 $x$。你可以假设输入中的数字不会重复。

输出格式

标准输出应打印恰好 $n$ 行。对应于输入中数字 $x$ 的行应包含 $repr(x) = (p, q)$，写为两个整数 $p$ 和 $q$，中间用单个空格分隔。

样例

输入 1

2
17
18

输出 1

6 3
16 15

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试组。