最近,Chanek 先生经常玩《Arena of Greed》游戏。顾名思义,游戏的目标是找到他们中最贪婪的人,然后他将被加冕为 Compfestnesia 之王。
游戏由两个人轮流进行,Chanek 先生先轮流进行。最初,有一个藏有$$$N$$$金币的宝箱。如果宝箱中没有更多金币,游戏结束。在每一回合中,玩家可以做出以下动作之一:
- 从宝箱中取出一枚金币。
- 拿走宝箱上一半的金币。仅当宝箱中的硬币数量为偶数时,此动作才可用。
两名玩家都会尝试最大化他们拥有的金币数量。查内克先生请求你帮助找出如果他和对手都发挥最佳的情况下他在游戏结束时可以获得的最大硬币数量。
输入
第一行包含一个整数 $$$T$$$ $$$(1 \le T \le 10^5)$$$ 表示测试用例的数量。
接下来的 $$$T$$$ 行每行包含一个整数 $$$N$$$ $$$(1 \le N \le 10^{18})$$$。
输出
$$$T$$$ 行,每一行都是 Chanek 先生要求的答案。
示例
输入 #1
2 5 6
输出 #1
2 4
注意
对于第一种情况,游戏如下:
1. Chanek 先生拿走了一枚硬币。
2. 对手拿走两枚硬币。
3. Chanek 先生拿走了一枚硬币。
4. 对手拿走一枚硬币。
对于第二种情况,游戏如下:
1. Chanek 先生拿走了三枚硬币。
2. 对手拿走一枚硬币。
3. Chanek 先生拿走了一枚硬币。
4. 对手拿走一枚硬币。