B. Уравнения математической магии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: $$$a - (a \oplus x) - x = 0$$$ для заданого $$$a$$$, где знаком $$$\oplus$$$ обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Ойра-Ойра быстро нашел $$$x$$$, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько существует неотрицательных решений данного уравнения. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные

Вам предстоит решить задачу для нескольких возможных значений параметра $$$a$$$. В первой строке находится целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество этих значений.

В последующих $$$t$$$ строках находятся значения параметра $$$a$$$, каждое значение — целое число от $$$0$$$ до $$$2^{30} - 1$$$ включительно.

Выходные данные

Для каждого значения параметра $$$a$$$ выведите строке одно целое число — количество неотрицательных решений уравнения с данным значением параметра. Ответы выводите в том же порядке, в каком параметры следуют во входных данных.

Можно доказать, что количество решений всегда конечно.

Пример
Входные данные
3
0
2
1073741823
Выходные данные
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$$$ это $$$i$$$-й бит числа $$$x$$$, а $$$y_i$$$ это $$$i$$$-й бит числа $$$y$$$.

Пусть $$$r = x \oplus y$$$ — результат операции XOR над числами $$$x$$$ и $$$y$$$. Тогда двоичной записью $$$r$$$ будет $$$r_k \dots r_2 r_1 r_0$$$, где:

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

Для первого значения параметра только $$$x = 0$$$ является решением уравнения.

Для второго значения параметра решениями уравнения являются $$$x = 0$$$ и $$$x = 2$$$.