题目描述

给定正整数 $n$，设集合 $S = \{1, 2, \ldots, n \}$，你可以执行下列操作恰好一次：

• 取一个非负整数 $x$，将 $S$ 中每个元素 $a$ 变为 $a \oplus x$，其中 $\oplus$ 为按位异或运算 $^\text{*}$ 。

设操作后得到的新集合为 $S^′$ ，求出 $\text{mex}(S^′)^†$ 可能的最大值。

$^{\text{*}}$ 按位异或运算指，对两个数的每个二进制位作不进位加法。

$^{\dagger}$ 对于整数集合 $f=\{f_1,f_2,\ldots,f_k\}$ ,$\operatorname{mex}(f)$ 定义为集合 $f$ 中未出现的最小非负整数。

输入格式

输入包含多个测试用例。

第一行输入一个正整数 $t\,(1\le t\le 10^4)$， 表示测试用例的数量。

对每个测试用例，输入一行一个正整数，表示给定的 $n\,(n\leq2\times10^5)$.

输入数据保证所有测试用例中 $n$ 的和不超过 $10^6$ .

输出格式

对于每个测试用例，输出一行一个正整数，表示 $\operatorname{mex}(S')$ 可能的最大值。

输入输出样例 #1

输入 #1

1
2

输出 #1

1

说明/提示

样例解释

初始集合为 $S=\{1,2\}$, 选择 $x=1$ 进行操作后得到 $S'=\{1 \oplus 1, 2 \oplus 1\}=\{0,3\}, \operatorname{mex} \{0,3\}=1$. 当然也可以选择 $x=2$ 进行操作，会得到同样的答案。可以证明，不存在更优的操作方法，故答案为 $1$.