题目内容

某资源分配系统需要将一个总量为 $S$ 的整数资源拆分成两个整数部分：第一部分为 $x$，第二部分为 $S-x$，其中 $0 \le x \le S$。定义该拆分的「分裂差异值」为 $D(x)=x \oplus (S-x)$，其中 $\oplus$ 表示按位异或运算，即两个二进制表示对应的位相同时结果为 0，不同时结果为 1。对于给定的每个总量 $S$，请计算所有合法拆分中可以取到的最小分裂差异值。

约束：询问个数不超过 10^5；每个总量 $S$ 满足 1 <= S <= 10^18。

输入描述

第一行包含一个整数 n，表示询问个数，满足 1 <= n <= 10^5。 接下来 n 行，每行包含一个整数 S，表示当前要处理的总量，满足 1 <= S <= 10^18。

输出描述

输出 n 行，每行一个非负整数，表示对应总量 $S$ 的最小分裂差异值。

样例1

输入

4
1
2
6
7

输出

1
0
0
7

说明

对于 $S=1$：合法拆分只有 $x=0, S-x=1$，因此 $D(0)=0 \oplus 1=1$，最小值为 1。

对于 $S=2$：取 $x=1$，此时 $S-x=1$，$1 \oplus 1=0$；由于异或非负，最小值为 0。

对于 $S=6$：偶数可以均分为 $3+3$，两个相同数异或为 0，因此最小值为 0。

对于 $S=7$：二进制为 $111_2$，均分为 $3$ 和 $4$，$3 \oplus 4 = 011_2 \oplus 100_2 = 111_2 = 7$，所以最小值为 7。

样例2

输入

3
9
15
18

输出

1
15
0

说明

对于 $S=9$：均分为 $4$ 和 $5$，$4 \oplus 5 = 100_2 \oplus 101_2 = 001_2 = 1$，因此最小值为 1。

对于 $S=15$：二进制 $1111_2$ 全为 1，均分为 $7$ 和 $8$，$7 \oplus 8 = 0111_2 \oplus 1000_2 = 1111_2 = 15$，最小值为 15。

对于 $S=18$：偶数可以均分为 $9+9$，两个相同数异或为 0，所以最小值为 0。

样例3

输入

2
1000000000000000000
576460752303423487

输出

0
576460752303423487

说明

对于 $S=10^{18}$：这是一个偶数，均分为 $500000000000000000$ 和 $500000000000000000$，两个相同数异或为 0，所以最小值为 0。

对于 $S=576460752303423487$：该数等于 $2^{59}-1$，二进制为连续的 59 个 1。均分为 $288230376151711743$ 和 $288230376151711744$，异或结果为 $576460752303423487$。这一类全 1 数的最小分裂差异值等于其本身。