最初,您有一枚价值 $$$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$$$ 的两个硬币。