Изначально у вас есть монета номиналом \(n\). Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):
- преобразовать одну монету номиналом \(x\), где \(x\) больше \(3\) (\(x>3\)), в две монеты номиналом \(\lfloor \frac{x}{4} \rfloor\).
Какое максимальное количество монет вы можете иметь после того, как выполните эту операцию любое количество раз?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которые вы можете иметь после выполнения операции любое количество раз.
Примечание
В первом примере у вас есть монета номиналом \(1\), и вы ничего не можете с ней сделать. Таким образом, ответ равен \(1\).
Во втором примере вы можете преобразовать монету номиналом \(5\) в две монеты номиналом \(1\).
В третьем примере вы можете преобразовать монету номиналом \(16\) в две монеты номиналом \(4\). Каждую из получившихся монет можно преобразовать в две монеты номиналом \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
5
16
1000000000000000000
|
1
2
4
536870912
|