← 返回题目列表

Codeforces · 2043/A

A. 硬币改造

中文机器翻译题面 查看原题

最初,您有一枚价值 $$$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}$$$)。

输出

对于每个测试用例,打印一个整数 - 执行任意次操作后可以获得的最大硬币数量。

示例

输入 #1

4
1
5
16
1000000000000000000

输出 #1

1
2
4
536870912

注意

在第一个示例中,您有一枚价值 $$$1$$$ 的硬币,并且您无法用它做任何事情。所以,答案是$$$1$$$。

在第二个示例中,您可以将价值 $$$5$$$ 的硬币转换为价值 $$$1$$$ 的两个硬币。

在第三个示例中,您可以将价值 $$$16$$$ 的硬币转换为价值 $$$4$$$ 的两枚硬币。每个生成的硬币都可以转化为价值 $$$1$$$ 的两个硬币。