题目背景

原题链接：https://oier.team/problems/X7G。

现在有一个序列。

这个序列第 $1$ 项为 $0$，第 $2$ 项为 $1$，第 $3$ 项为 $1$，第 $4$ 项为 $3$。

现在 @lxwtr 问你第 $n$ 项的值为多少。

题目描述

Alice 和 Bob 找到了一个棋盘。棋盘可以看成一个数轴，初始时在原点处有 $n$ 个棋子。令 $a_i$ 表示数轴下标为 $i$ 的位置的棋子数量（原点 $i=0$），操作者每次会找到最小的满足 $a_i\ge 2$ 的 $i$，令 $a_i$ 减去 $2$ 并选择令 $a_{i+1}$ 加上 $1$ 或令 $a_{i+2}$ 加上 $1$。由 Alice 先手，二人轮流操作。操作者必须操作，如果无法找到这样的 $i$ 则立即结束游戏。

Alice 希望二人的总操作次数最少，Bob 希望二人的总操作次数最多，二人都是绝对聪明的。二人一共进行了 $T$ 次游戏，你希望知道每次游戏最终二人一共会进行多少次操作。

输入格式

第一行，一个正整数 $T$，表示进行的游戏次数。

接下来 $T$ 行，每行一个正整数 $n$，表示每次游戏开始时，原点的棋子个数。

输出格式

共 $T$ 行，第 $i$ 行一个非负整数，表示第 $i$ 次游戏最终二人一共会进行多少次操作。

6
1
2
3
4
100
100000

0
1
1
3
95
99989

提示

【样例解释】

对于第一次游戏，原点棋子数为 $1$，无法进行操作。

对于第二次游戏，可以恰好进行一次操作之后使得 $a_1=1$ 或 $a_2=1$。无论哪一种都无法继续操作。

对于第三次游戏，类似第二次游戏，额外在原点留下了一个棋子。

对于第四次游戏，第一次操作无论 Alice 操作后将棋子放在哪个位置，Bob 都可以放在那个位置，这样 Alice 会再进行一次操作。总共 $3$ 次操作。

【数据范围】

本题采用捆绑测试。

• 子任务 1（5 分）：$n\le16$。
• 子任务 2（6 分）：$n\le 50$。
• 子任务 3（14 分）：$n\le 200$。
• 子任务 4（20 分）：$n\le 5000$。
• 子任务 5（21 分）：$n\le 10^5$。
• 子任务 6（34 分）：无特殊性质。

对于全部的数据，$1\le T\le 500$，$1\le n\le 10^{18}$。