C. 前缀异或
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

如果一个非负整数的二进制表示中 $$$1$$$ 的个数是一个质数$$$^{\text{∗}}$$$，则称这个非负整数是一个「好数」。例如，$$$3$$$（二进制为 $$$(11)_2$$$，包含 $$$2$$$ 个 $$$1$$$）和 $$$7$$$（二进制为 $$$(111)_2$$$，包含 $$$3$$$ 个 $$$1$$$）都是「好数」，而 $$$1$$$（包含 $$$1$$$ 个 $$$1$$$）和 $$$15$$$（二进制为 $$$(1111)_2$$$，包含 $$$4$$$ 个 $$$1$$$）都不是「好数」。

定义 $$$f(k) = 1 \oplus 2 \oplus \cdots \oplus k$$$，其中 $$$\oplus$$$ 表示按位异或运算$$$^{\text{†}}$$$。

给定一个正整数 $$$N$$$，请你求出小于 $$$N$$$ 的最大的正整数 $$$k$$$，使得 $$$f(k)$$$ 是一个「好数」。

$$$^{\text{∗}}$$$质数是只有两个不同的正因数的自然数。例如 $$$2$$$、$$$3$$$、$$$5$$$、$$$7$$$、$$$11$$$ 都是质数，而 $$$0$$$、$$$1$$$、$$$4$$$、$$$6$$$、$$$8$$$、$$$9$$$ 都不是质数。

$$$^{\text{†}}$$$按位异或是一种二进制位运算：将两个整数写成二进制后逐位比较，对应位不同则结果的该位为 $$$1$$$，相同则为 $$$0$$$。例如 $$$5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$$$。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \le T \le 10^5$$$），表示测试用例的数量。对于每组测试用例：

  • 仅一行，包含一个整数 $$$N$$$（$$$3 \le N \le 10^{18}$$$），含义如题面所述。
Output

对于每组测试用例，输出一行，包含一个整数 $$$k$$$，表示小于 $$$N$$$ 且满足 $$$f(k)$$$ 是「好数」的最大正整数。

Example
Input
4
3
5
13
70368744177658
Output
2
2
12
70368744177656
Note

对于第一组测试用例，$$$N = 3$$$，小于 $$$3$$$ 的正整数只有 $$$1$$$ 和 $$$2$$$。$$$f(1) = 1$$$，包含 $$$1$$$ 个 $$$1$$$，不是「好数」；$$$f(2) = 1 \oplus 2 = 3$$$，二进制为 $$$(11)_2$$$，包含 $$$2$$$ 个 $$$1$$$，是「好数」，因此答案为 $$$2$$$。

对于第二组测试用例，$$$N = 5$$$。从大到小依次检验：$$$f(4) = 4$$$，包含 $$$1$$$ 个 $$$1$$$；$$$f(3) = 0$$$，包含 $$$0$$$ 个 $$$1$$$，都不是「好数」；$$$f(2) = 3$$$，是「好数」，因此答案为 $$$2$$$。

对于第三组测试用例，$$$N = 13$$$。$$$12$$$ 是小于 $$$13$$$ 的最大正整数，且 $$$f(12) = 12$$$，二进制为 $$$(1100)_2$$$，包含 $$$2$$$ 个 $$$1$$$，是「好数」，因此答案为 $$$12$$$。