Background

Special for beginners, ^_^

Description

有一棵无限的完全二叉搜索树，节点中的数字是$1,2,3……$如下图所示。在根节点为$X$的子树中，可以从左侧节点向下，直到最后一级获得该子树中的最小数，也可以从右侧节点向下找到该子树中的最大数。求解$X$的子树中的最小数和最大数是多少。

Format

Input

第$1$行包含一个整数$N$，表示查询的数量。在接下来的$N$行中，每行都包含一个数字，表示根号为$X$的子树$（1<=X<=2e31-1）$。

Output

共$N$行，其中第i行包含第i个查询的答案。

Samples

2
8
10

1 15
9 11