该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 5D. 最贪心的人

时间限制：1000ms

空间限制：256MB

Description

小周和小季两个人轮流玩一个游戏，小周先开始。最初，有一个宝箱，里面有 \(N\) 个金币。如果箱子里没有金币时，游戏就结束。

在每个回合中，玩家可以做出以下动作之一：

• 从箱子里拿出一枚金币。
• 取箱子中金币的一半，只有当箱子里的硬币数量是偶数时才可执行。

小周和小季都会试图最大化他们所拥有的硬币数量。小周希望你帮助他找出在游戏结束时，如果他和对手都玩得最优，他能得到的最大金币数。

Input Format

第一行包含单个整数 \(T (1≤T≤10^5)\) 表示测试用例的数量。

接下来的 \(T\) 行每行包含一个整数 \(N (1≤N≤10^{18})\) 。

Output Format

输出 \(T\) 行，每行要求如上。

Test Case 1

input

2
5
6

output

2
4

Note

对于第一种情况，游戏如下:

1. 小周拿了一个金币
2. 小季拿了两个金币
3. 小周拿了一个金币
4. 小季拿了一个金币