区块链技术被应用于许多数字货币系统中，例如比特币和以太坊。在这种技术中，分布式用户共享一个公共的记录列表（称为链），用户通过解决数学问题获得向链中添加新记录的权利。这个过程被称为“挖矿”。$i$-Taiwan 公司开发了一种新的数字货币系统，称为 ICPC（I-taiwan Coins for the Public Currency）。在 ICPC 系统中，其挖矿的数学问题如下：给定正整数 $n$，该问题要求找到最大的整数 $a$，使得对于某个正整数 $b$，满足： $$\frac{1}{n} = \frac{1}{a \oplus b} + \frac{1}{b}$$ 其中 $\oplus$ 是按位异或运算符。例如，对于 $n = 12$，其解为 $a = 145$。在这种情况下，$b = 13$，因此 $a \oplus b = 145 \oplus 13 = 10010001_2 \oplus 1101_2 = 10011100_2 = 156$。相应地， $$\frac{1}{a \oplus b} + \frac{1}{b} = \frac{1}{156} + \frac{1}{13} = \frac{1}{12} = \frac{1}{n}$$ 你是一位雄心勃勃的程序员，想要在短时间内从该系统中挖掘出大量的数字货币。请编写一个程序，为每个 $n$ 找到最大的 $a$，以便从 ICPC 获得奖励。

输入格式

输入文件的第一行包含一个正整数 $T$，表示测试用例的数量。在接下来的 $T$ 行中，每一行对应一个测试用例，并指定整数 $n$。

输出格式

对于每个测试用例，输出最大的整数 $a$，占一行。

数据范围

• $1 \le T \le 20$
• $0 < n \le 10^7$

样例

样例输入 1

3
6
7
10

样例输出 1

45
48
101

样例输入 2

3
1
2
7777777

样例输出 2

0
5
60493819864864