ZHY发现了一个有趣的式子：a-(a⊕x)-x=0。其中⊕表示两个整数按位异或(XOR)(此操作在许多现代编程语言中表示为^或xor)。
对与某个给定的a，HSQ很快发现了一些x是这个等式的解，但ZHY觉得HSQ的结果不够有趣，所以他问HSQ对于某个给定的a，x有多少个非负解。
对于HSQ来说这个任务太难了，所以他请你帮忙。每个测试都包含了几个可能的a值，你的任务是找到每个方程解的数量。
异或
Input
第一行包含一个整数T，表示有T组测试数据。
接来下T行，每行有一个整数a(0 ≤ a ≤ (2^30-1))。
接来下T行，每行有一个整数a(0 ≤ a ≤ (2^30-1))。
Output
对于每个输入的a值，输出一个整数表示该式子的非负整数解的数量。
可以发现解决方案的数量总是有限的。
可以发现解决方案的数量总是有限的。
Sample Input
3
0
2
1073741823Sample Output
1
2
1073741824HINT
按位异或(XOR)运算的定义。给出两个整数x和y，考虑它们的二进制表示(可能带有前导0)：x[k]...x[2]x[1]x[0]和y[k]...y[2]y[1]y[0].
在这里，x[i]是x的第i个二进制位，y[i]是y的第i个二进制位。定义r=x⊕y，r的二进制位为r[k]...r[2]r[1]r[0]。
如果x[i] == y[i],那么r[i] = 0；如果x[i] != y[i],那么r[i] = 1 。
对于样例的第一个值，只有 x = 0 是等式的解。
对于样例的第二个值，解是 x = 0 和 x = 2 。