阅读《数学魔法方程》一书 Roman Oira-Oira 和 Cristobal Junta 发现了一个有趣的方程: $$$a - (a \oplus x) - x = 0$$$ 对于某些给定的 $$$a$$$,其中 $$$\oplus$$$ 代表两个整数的按位异或 (XOR)(此操作在许多现代编程中表示为 ^ 或 xor)语言)。 Oira-Oira很快找到了一些$$$x$$$,这就是方程的解,但是Cristobal Junta认为Oira-Oira的结果不够有趣,所以他问他的同事这个方程存在多少个非负解。这个任务对奥伊拉-奥伊拉来说太困难了,所以他请你帮忙。
输入
每个测试都包含 $$$a$$$ 的几个可能值,您的任务是找到每个值的方程解的数量。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 这些值的数量。
以下 $$$t$$$ 行包含参数 $$$a$$$ 的值,每个值都是从 $$$0$$$ 到 $$$2^{30} - 1$$$ 的整数(包含在内)。
输出
对于 $$$a$$$ 的每个值,仅打印一个整数 - 给定参数值的方程非负解的数量。按照与输入中出现的 $$$a$$$ 值相同的顺序打印答案。
可以证明解的数量始终是有限的。
示例
输入 #1
3 0 2 1073741823
输出 #1
1 2 1073741824
注意
让我们定义按位异或 (XOR) 运算。给定两个整数 $$$x$$$ 和 $$$y$$$,考虑它们的二进制表示形式(可能带有前导零):$$$x_k \dots x_2 x_1 x_0$$$ 和 $$$y_k \dots y_2 y_1 y_0$$$。这里,$$$x_i$$$是数字$$$x$$$的第$$$i$$$位,$$$y_i$$$是数字$$$y$$$的第$$$i$$$位。设 $$$r = x \oplus y$$$ 为 $$$x$$$ 和 $$$y$$$ 异或运算的结果。然后 $$$r$$$ 定义为 $$$r_k \dots r_2 r_1 r_0$$$ 其中:
$$$$$$ r_i = \left\{ \begin{aligned} 1, ~ \text{if} ~ x_i \ne y_i \\ 0, ~ \text{if} ~ x_i = y_i \end{aligned} \right。 $$$$$$
对于参数的第一个值,只有 $$$x = 0$$$ 是方程的解。
对于参数的第二个值,解决方案是 $$$x = 0$$$ 和 $$$x = 2$$$。