题目描述

给定一个数列 $a$：

• 当 $n\le 2$ 时，$a_n=n$。
• 当 $n>2$，且 $n$ 是奇数时， $a_n=2\times a_{n-1}$。
• 当 $n>2$，且 $n$ 是偶数时，$a_n=a_{n-1}+r_{n-1}$。

其中 $r_{n-1}= \operatorname{mex}(|a_i-a_j|)(1\le i\le j\le n-1)$， $\operatorname{mex} \left\{ S\right\}$ 表示最小的不在 $S$ 集合里面的非负整数。

数列 $a$ 的前若干项依次为：

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

可以证明，对于任意正整数 $x$，只存在唯一一对整数 $(p,q)$ 满足 $x=a_p-a_q$，定义为 $\operatorname{repr}(x)$。

比如 $\operatorname{repr}(17)=(6,3)$，$\operatorname{repr}(18)=(16,15)$。 现有 $n$ 个询问，每次给定一个正整数 $x$，请求出 $\operatorname{repr}(x)$。

输入格式

第一行包含一个正整数 $n$。

接下来 $n$ 行，每行一个正整数 $x$，表示一个询问。

输出格式

输出 $n$ 行，每行两个正整数 $p,q$，依次回答每个询问。

2
17
18

6 3
16 15

提示

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le x\le 10^9$。