A. Преобразование монет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Изначально у вас есть монета номиналом $$$n$$$. Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):

  • преобразовать одну монету номиналом $$$x$$$, где $$$x$$$ больше $$$3$$$ ($$$x>3$$$), в две монеты номиналом $$$\lfloor \frac{x}{4} \rfloor$$$.

Какое максимальное количество монет вы можете иметь после того, как выполните эту операцию любое количество раз?

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей одно целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

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

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

Пример
Входные данные
4
1
5
16
1000000000000000000
Выходные данные
1
2
4
536870912
Примечание

В первом примере у вас есть монета номиналом $$$1$$$, и вы ничего не можете с ней сделать. Таким образом, ответ равен $$$1$$$.

Во втором примере вы можете преобразовать монету номиналом $$$5$$$ в две монеты номиналом $$$1$$$.

В третьем примере вы можете преобразовать монету номиналом $$$16$$$ в две монеты номиналом $$$4$$$. Каждую из получившихся монет можно преобразовать в две монеты номиналом $$$1$$$.