题目描述

最开始，你有一枚价值为 $n$ 的硬币。你可以任意多次地执行以下操作：

• 将一枚价值为 $x$ 的硬币（其中 $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$ 的硬币，无法进行任何转换。所以，答案是 $1$。

在第二个例子中，你可以把一枚价值为 $5$ 的硬币转化为两枚价值为 $1$ 的硬币。

在第三个例子中，你可以把一枚价值为 $16$ 的硬币转化为两枚价值为 $4$ 的硬币。然后，每枚价值为 $4$ 的硬币可以继续转化成两枚价值为 $1$ 的硬币。