P11565 【MX-X7-T6】[LSOT-3] 棋盘

原题链接：。 现在有一个序列。 这个序列第 $1$ 项为 $0$，第 $2$ 项为 $1$，第 $3$ 项为 $1$，第 $4$ 项为 $3$。 现在 [@lxwtr](https://www.luogu.com.cn/discuss/875194) 问你第 $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$ 次游戏，你希望知道每次游戏最终二人一共会进行多少次操作。

无

无

**【样例解释】** 对于第一次游戏，原点棋子数为 $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}$。