CF1425A.Arena of Greed

Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing $N$ gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:

• Take one gold coin from the chest.
• Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even.

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.

最近，Chanek 先生经常玩一款名为《贪婪竞技场》的游戏。顾名思义，该游戏的目标是找出所有人中最贪婪者，该人将被加冕为 Compfestnesia 的国王。

游戏由两人轮流进行，Chanek 先生先手。初始时，宝箱中装有 $N$ 枚金币。当宝箱中不再有金币时，游戏结束。在每一轮中，玩家可执行以下两种操作之一：

• 从宝箱中取走 1 枚金币；
• 取走宝箱中一半的金币。此操作仅在宝箱中金币数量为偶数时方可执行。

双方均会尽力使自己最终获得的金币数量最大化。Chanek 先生请求你帮助计算：若他与对手均采取最优策略，他最多能获得多少枚金币？

The first line contains a single integer $T$ $(1 \le T \le 10^5)$ denotes the number of test cases.

The next $T$ lines each contain a single integer $N$ $(1 \le N \le 10^{18})$.

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

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

$T$ lines, each line is the answer requested by Mr. Chanek.

$T$ 行，每行是陈先生要求的答案。

For the first case, the game is as follows:

1. Mr. Chanek takes one coin.
2. The opponent takes two coins.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

For the second case, the game is as follows:

1. Mr. Chanek takes three coins.
2. The opponent takes one coin.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

对于第一种情况，游戏过程如下：

1. 陈先生取走一枚硬币。
2. 对手取走两枚硬币。
3. 陈先生取走一枚硬币。
4. 对手取走一枚硬币。

对于第二种情况，游戏过程如下：

1. 陈先生取走三枚硬币。
2. 对手取走一枚硬币。
3. 陈先生取走一枚硬币。
4. 对手取走一枚硬币。