题目描述

现给定一个 $n$ ，请你求出 $0$ ~ $n$ 中的每个 $i$ 满足 $i \bigoplus n =i\mid n$ （即 $i$ 与 $n$ 的异或值等于 $i$ 与 $n$ 的按位或）等式的 $i$ 的个数。

$\bigoplus$ 表示异或：二进制位相同为 $0$，不同为 $1$

$\mid$ 表示或：二进制位有 $1$ 是 $1$ ，全 $0$ 才是 $0$

如：

$2 \bigoplus 3 = (010)_2 \bigoplus (011)_2 = (001)_2=1$

$2 \mid 3 = (010)_2 \mid (011)_2 = (011)_2=3$

输入格式

第一行一个整数 $T$（$1\le T \le 10^4$） ，代表 $T$ 组测试样例。

接下来的 $T$ 行，每行一个正整数 $n$（$0\le n \le10^{18}$） 。

输出格式

输出 $T$ 行，每行一个整数代表满足条件的个数。

输入样例

3
0
1
2

输出样例

1
1
2

提示

$n=0$ 时：只有 $0$ 满足条件

$n=1$ 时：只有 $0$ 满足条件

$n=2$ 时：有 $0,1$ 满足条件