最大公约数和按位运算有什么共同点吗?是时候回答这个问题了。
假设给你一个正整数 $$$a$$$。您想要从 $$$1$$$ 到 $$$a - 1$$$ 之间选择一些整数 $$$b$$$,其中整数 $$$a \oplus b$$$ 和 $$$a \> \& \> b$$$ 的最大公约数 (GCD) 尽可能大。换句话说,您想要计算以下函数:
$$$$$$f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}.$$$$$$
这里$$$\oplus$$$表示按位异或运算,$$$\&$$$表示按位与运算。
两个整数 $$$x$$$ 和 $$$y$$$ 的最大公约数是最大整数 $$$g$$$,使得 $$$x$$$ 和 $$$y$$$ 都除以 $$$g$$$ 而没有余数。
给你 $$$q$$$ 整数 $$$a_1, a_2, \ldots, a_q$$$。对于每个整数,计算最大公约数的最大可能值(当 $$$b$$$ 被最佳选择时)。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^3$$$) — 您需要计算答案的整数个数。
之后给出 $$$q$$$ 整数,每行一个:$$$a_1, a_2, \ldots, a_q$$$ ($$$2 \le a_i \le 2^{25} - 1$$$) - 您需要计算答案的整数。
输出
对于每个整数,按照输入中给出的整数相同的顺序打印答案。
示例
输入 #1
3 2 3 5
输出 #1
3 1 7
注意
对于第一个整数,最佳选择是 $$$b = 1$$$,然后 $$$a \oplus b = 3$$$、$$$a \> \& \> b = 0$$$,$$$3$$$ 和 $$$0$$$ 的最大公约数是 $$$3$$$。
对于第二个整数,最佳选择是 $$$b = 2$$$,则 $$$a \oplus b = 1$$$、$$$a \> \& \> b = 2$$$,$$$1$$$ 和 $$$2$$$ 的最大公约数是 $$$1$$$。
对于第三个整数,最佳选择是 $$$b = 2$$$,则 $$$a \oplus b = 7$$$、$$$a \> \& \> b = 0$$$,$$$7$$$ 和 $$$0$$$ 的最大公约数是 $$$7$$$。