Arena of Greed

题意翻译

最初，有一个宝箱，里面装着 $N$ 枚金币。如果箱子里没有金币，游戏就结束了。在每一回合中，玩家可以进行以下动作之一： 1.从箱子里拿出一枚金币。 2.把箱子上一半的金币拿走。只有当箱子里的硬币数是偶数时，这个移动才可用。 两个玩家都会尽量使他们拥有的硬币数量最大化。查内克先生请你帮忙找出在游戏结束时他能得到的硬币的最大数量，如果他和对手都玩得很好。

题目描述

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.

输入输出格式

输入格式

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 $ lines, each line is the answer requested by Mr. Chanek.

输入输出样例

输入样例 #1

2
5
6

输出样例 #1

2
4

说明

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.