No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一棵无限的完全二叉树，节点中的数字是 1，2，3 ... 如下图所示。

在根结点为 X 的子树中，可以从左侧结点向下，直到最后一级获得该子树中的最小数，也可以从右侧结点向下找到该子树中的最大数。求解 X 的子树中的最小数和最大数是多少。

Format

Input

第一行包含一个整数 N，表示查询的数量。

在接下来的 N 行中，每行都包含一个数字，表示根号为 X 的子树。($1 ≤ X ≤ 2^{31}-1$)

Output

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

Samples

2
8
10

1 15
9 11

Limitation

1s, 1024KiB for each test case.