解题思路

定义回顾：把正整数写成二进制（无前导 0）。若其中 1 的个数等于 0 的个数，则称为完美数。 设总位数为 L，则必须有 L 为偶数，且 #1 = #0 = L/2。同时最高位必须为 1（无前导 0）。

核心观察

1. 任意完美数的二进制长度一定是偶数 L=2k，并且最高位为 1、总 1 的个数为 k。
2. 对于固定长度 2k，最小的完美数是把除最高位外的 (k-1) 个 1 全放在最低位： 形如 1 0^k 1^(k-1)，数值即

题目内容

给定一个正整数的二进制表示(不含前导 $0$ )中，$1$ 的个数为 $n$ ，$0$ 的个数为 $m$ 。

若满足 $m=n$

则称该整数为完美数。

现给定一个整数 $x$ ，请找出大于等于 $x$ 的最小完美数。

【名词解释】

• 二进制表示：二进制表示指将一个正整数按基数 $2$ 形式书写，不含前导零。例如，$5$ 的进制表示为 $(101)_2$ 。

• 完美数：完美数指其二进制表示中 $1$ 的个数与 $0$ 的个数相等。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^5)$ 代表数据组数，每组测试数据描述如下：

每行输入一个整数 $x(1≤x≤10^9)$ 。

输出描述

对于每，组测试数据，新起一行，输出一个整数，表示不小于 $x$ 的最小完美数。

样例1

输入

6
1
2
3
4
5
6

输出

2
2
9
9
9
9

说明

• 当 $x=1$ 时，最小完美数为 $2$ (二进制 $(10)_2$ ，中 $1,0$ 均为 $1$ ）。

• 当 $x=2$ 时，最小完美数为 $2$ 。

• 当 $3≦x≦6$ 时，最小完美数为 $9$ (二进制 $(1001)_2$，中 $1,0$ 均为 $2$ )。

样例2

输入

3
8
9
10

输出

9
9
10