题目内容

调度模块要把一个非负整型额度 $m$ 拆成两份：任选整型 $y$（$0 \le y \le m$），另一份为 $m-y$。定义这次拆分的「对冲值」为

其中 $\oplus$ 为按位异或（对应二进制位相同得 $0$、不同得 $1$）。例如 $6\ (110_2)$ 与 $1\ (001_2)$ 满足 $6\ \text{xor}\ 1 = 7\ (111_2)$。现给定若干个额度，请对每个 $m$ 求出可取到的最小对冲值。

输入描述

第一行一个整型 $n$ $(1 \le n \le 10^5)$，表示随后有 $n$ 行额度。

接下来 $n$ 行，每行一个整型 $m$ $(1 \le m \le 10^{18})$。

请对每个 $m$ 逐一计算其最小对冲值。

输出描述

共输出 $n$ 行；对于每一个 $m$，写出一个非负整型，即

样例1

输入

3
4
5
11

输出

0
1
3

说明

三个额度依次为 $4,5,11$：取 $y=2$ 时 $2\oplus 2=0$；取 $y=2$ 时 $2\oplus 3=1$；取 $y=4$ 时 $4\oplus 7=3$。

样例2

输入

2
2
7

输出

0
7

说明

额度 $2$：取 $y=1$ 得 $1\oplus 1=0$。额度 $7$：枚举可知最小对冲值为 $7$。