题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Reprezentacje różnicowe

我们来定义一个无穷整数序列 $a_1, a_2, a_3, \ldots$，规则如下：

$$a_n = \begin{cases} n & \text{若 } n \leq 2 \\ 2 \cdot a_{n-1} & \text{若 } n > 2 \text{ 且为奇数} \\ a_{n-1} + r_{n-1} & \text{若 } n > 2 \text{ 且为偶数} \end{cases} $$

其中 $r_{n-1}$ 是集合 $\{a_1, a_2, \ldots, a_{n-1}\}$ 中任意两个不同元素之差未出现过的最小正整数。

序列的前几项是：

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

举个例子，要算 $a_6$，我们先看前五项 $1, 2, 4, 8, 16$。它们的差值包括 $1, 2, 3, 4$，但 $5$ 未出现，因此 $a_6 = a_5 + 5 = 21$。

已知对于任意正整数 $x$，都存在唯一一对下标 $(p, q)$ 满足 $x = a_p - a_q$，记为 $\operatorname{repr}(x)$。比如 $\operatorname{repr}(17) = (6, 3)$，$\operatorname{repr}(18) = (16, 15)$。你的任务是为给定的 $x$ 找出 $\operatorname{repr}(x)$。

输入格式

输入第一行是一个整数 $n$，表示测试数据数量。

接下来的 $n$ 行，每行一个正整数 $x$。假设输入中的数不重复。

输出格式

输出 $n$ 行，每行对应输入中的 $x$，包含 $\operatorname{repr}(x) = (p, q)$，以两个整数 $p$ 和 $q$ 表示。

样例

输入

2
17
18

输出

6 3
16 15

解释
对于 $17$，$a_6 - a_3 = 21 - 4 = 17$，所以 $\operatorname{repr}(17) = (6, 3)$；
对于 $18$，$a_{16} - a_{15} = 990 - 972 = 18$，所以 $\operatorname{repr}(18) = (16, 15)$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
1	$n \leq 1000$，$x \leq 10^{9}$，结果 $p$ 和 $q$ 不超 $100$	$20$
2	$n, x \leq 1000$
3	$n, x \leq 1000000$
4	$n \leq 100000$，$x \leq 10^{9}$	$40$