E. Уравнения математической магии

Для заданного $a$ посчитайте количество неотрицательных решений уравнения

Перепишем его как $a \oplus x = a - x$. Дальше всё решает одно наблюдение про исключающее «или».

Первая строка содержит число $t$ ($1 \le t \le 1000$).

Далее идут $t$ строк со значениями $a$ ($0 \le a \le 2^{30} - 1$).

$t$ строк — количество решений для каждого $a$.