Colossal! — exclaimed Hawk-nose. — A programmer! That's exactly what we are looking for.Arkadi and Boris Strugatsky. Monday starts on Saturday

Reading the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta found an interesting equation: $a - (a \oplus x) - x = 0$ for some given $a$, where $\oplus$ stands for a bitwise exclusive or (XOR) of two integers (this operation is denoted as ^ or xor in many modern programming languages). Oira-Oira quickly found some $x$, which is the solution of the equation, but Cristobal Junta decided that Oira-Oira's result is not interesting enough, so he asked his colleague how many non-negative solutions of this equation exist. This task turned out to be too difficult for Oira-Oira, so he asks you to help.


-----Input-----

Each test contains several possible values of $a$ and your task is to find the number of equation's solution for each of them. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of these values.

The following $t$ lines contain the values of parameter $a$, each value is an integer from $0$ to $2^{30} - 1$ inclusive.


-----Output-----

For each value of $a$ print exactly one integer — the number of non-negative solutions of the equation for the given value of the parameter. Print answers in the same order as values of $a$ appear in the input.

One can show that the number of solutions is always finite.


-----Example-----
Input
3
0
2
1073741823

Output
1
2
1073741824



-----Note-----

Let's define the bitwise exclusive OR (XOR) operation. Given two integers $x$ and $y$, consider their binary representations (possibly with leading zeroes): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$. Here, $x_i$ is the $i$-th bit of the number $x$ and $y_i$ is the $i$-th bit of the number $y$. Let $r = x \oplus y$ be the result of the XOR operation of $x$ and $y$. Then $r$ is defined as $r_k \dots r_2 r_1 r_0$ where:

$$ r_i = \left\{ \begin{aligned} 1, ~ \text{if} ~ x_i \ne y_i \\ 0, ~ \text{if} ~ x_i = y_i \end{aligned} \right. $$

For the first value of the parameter, only $x = 0$ is a solution of the equation.

For the second value of the parameter, solutions are $x = 0$ and $x = 2$.

Difficulty: interview

Starter code:

Solutions:
import sys
import string
from math import gcd
import getpass
import math
from decimal import Decimal


def ria():
    return [int(i) for i in input().split()]


if getpass.getuser() != 'frohenk':
    filename = 'half'
    # sys.stdin = open('input.txt')
    # sys.stdout = open('output.txt', 'w')
else:
    sys.stdin = open('input.txt')
    # sys.stdin.close()
# sys.stdout = open('input.txt','w')

n = ria()[0]
for i in range(n):
    print(2 ** str(bin(int(input()))).count('1'))


def countSetBits(num): 
  
     
     binary = bin(num) 
  
    
     setBits = [ones for ones in binary[2:] if ones=='1'] 
       
     return len(setBits)
t=int(input())
for _ in range(t):
    n=int(input())
    x=countSetBits(n)
    print(2**x)



def solve():
    a = int(input())
    print(2**(bin(a)[2:].count('1')))
    
for _ in range(int(input())):
    solve()

# Author: πα

n = int(input())
for i in range(n):
    b = bin(int(input()))
    count = 0
    for c in b:
        if c == '1':
            count += 1
    print(pow(2, count))

USE_STDIO = False

if not USE_STDIO:
    try: import mypc
    except: pass

def count_bits(x):
    ans = 0
    while x:
        ans += 1
        x &= x - 1
    return ans

def main():
    t,  = list(map(int, input().split(' ')))
    for _ in range(t):
        a, = list(map(int, input().split(' ')))
        c = count_bits(a)
        ans = 1 << c
        print(ans)


def __starting_point():
    main()




__starting_point()

t = int(input())
for _ in range(t):
    a = int(input())
    print(2**(str(bin(a)).count('1')))


t = int(input())
for _ in range(t):
	x = int(input())
	res = 0
	while x:
		res += (x & 1)
		x >>= 1
	print(1 << res)

from sys import stdin,stdout,exit,setrecursionlimit
def sin(): 
	return stdin.readline().rstrip()
def listInput():
	return list(map(int,sin().split()))
def printBS(li):
	if not li: return
	for i in range(len(li)-1):
		stdout.write("%d "%(li[i]))
	stdout.write("%d\n"%(li[-1]))

t= int(sin())
for _ in range(t):
	a=int(sin())
	s=str(bin(a))[2:]
	print(2**(s.count('1')))

def count_ones(x):
    ans = 0
    while (x > 0):
        if x % 2 == 1:
            ans = ans + 1
        x  = x // 2
    return ans

t = int(input())
for i in range(t):
    a = int(input())
    y = count_ones(a)
    print(2 ** y)

t = int(input())
for i in range(t):
    a = int(input())
    num = 1
    for j in range(30):
        if a & 1 << j:
            num *= 2
    print(num)

for _ in range(int(input())):
    print(pow(2, bin(int(input())).count('1')))

def ans():
    n = int(input())
    c = bin(n).count("1")
    ans = pow(2, c)

    print(ans)

tc = int(input())
for _ in range(tc):
    ans()

t = int(input())

for _ in range(t):
    a = int(input())
    ans = 2**sum([(a >> i) & 1 for i in range(32)]) 
    print(ans)


for i in range(int(input())):
    n=int(input())
    b=list(bin(n))[2:]
    ans=1
    for i in b:
        if i=='1':
            ans*=2
    print(ans)


for _ in range(int(input())):
	n = int(input())
	print((2**bin(n)[2:].count('1')-1)+1)

t=int(input())
for i in range(t):
    s=0
    a=int(input())
    while a!=0:
        if a%2==1:
            s+=1
        a=a//2
    print(2**s)

t = int(input())
for i in range(t):
    ans = 1
    a = bin(int(input()))[2:]
    for j in a:
        if j == '1':
            ans *= 2
    print(ans)

n = int(input())
for _ in range(n):
    a = int(input())
    print(2 ** bin(a).count("1"))


def solve(n):
    res = 0
    for x in range(n + 1):
        if n^x == n - x:
            res += 1
    return res

def solve_1(n):
    cnt = 0
    while n:
        if n %2 == 1:
            cnt += 1
        n = n//2 
    return 2**cnt

t = int(input())
while t:
    n = int(input())
    print(solve_1(n))
    t -= 1


t = int(input())
for i in range(t):
    p = int(input())
    print(2**bin(p).count('1'))

def solve(x):
    k = 0
    while x > 0:
        if (x % 2 == 1):
            k += 1
        x //= 2
    return (2**k)
l = int(input())
ar = []
for i in range(l):
    ar.append(int(input()))
for i in range(l):
    print(solve(ar[i]))


for i in range(int(input())):
    a=int(input())
    m=bin(a)
    k=1
    for i in m[2:]:
        if i=='1':
            k*=2
    print(k)
    


import sys

def minp():
	return sys.stdin.readline().strip()

t = int(minp())
for i in range(t):
	a = int(minp())
	c = 0
	while a > 0:
		if a & 1 != 0:
			c += 1
		a >>= 1
	print(2**c)


T=int(input())
for t in range(T):
    a=int(input())
    cnt=0
    while a!=0:
        if a%2==1:cnt+=1
        a>>=1
    print(1<<cnt)


n = int(input())
for i in range(n):
    x = int(input())
    ans = 1
    for j in range(33):
        if (1<<j)&x:
            ans *= 2
    print(ans)