题目描述

考虑一棵无限的满二叉搜索树（如下图所示），树中节点的编号依次为$1, 2, 3, \ldots$。对于以节点$X$为根的子树，我们可以通过不断向左子节点向下遍历直到最后一层得到该子树中的最小编号，同样地，通过不断向右子节点向下遍历可以得到最大编号。现在给定若干查询，每个查询给出一个节点编号$X$，要求回答以$X$为根的子树中的最小和最大编号。

输入格式

• 第一行包含一个整数$N$，表示查询的数量。
• 接下来的$N$行，每行包含一个整数$X$（$1 \leq X \leq 2^{31}-1$），表示查询的子树的根节点编号。

输出格式

• 输出$N$行，每行对应一个查询的结果，格式为最小编号 最大编号。

样例输入

2  
8  
10  

样例输出

1 15  
9 11  

POJ Monthly（POJ月赛），Minkerui（命题人：Minkerui）