（这个题好厉害，让我感叹 MXOJ 比赛的质量）

不妨设 $f_{i, j, k, 0/1}$ 表示此时最小的可操作位置上面有 $i$ 个棋子，下一个位置有 $j$ 个，再下一个位置有 $k$ 个棋子，需要最小/最大化操作数时的答案。

这个状态的转移中，只要 $i \geq 2$ 就会一直让 $i \larr i - 2$ 并让 $j \larr j + 1$ 或 $k \larr k + 1$（取较优的那个），知道 $i$ 变成 $1$ 或者 $0$。所以说不妨去掉 $k$ 一维，直接考虑 $f_{i, j, 0, 0/1} \to f_{i', j', 0, 0/1}$。

此时状态记作 $f_{i, j, op}$。令 $t = \lfloor \frac{i}{2} \rfloor, nxtop = op \oplus [t \bmod 2 = 1]$，则有转移 $f_{i, j, op} \larr t + f_{j + x, t - x, nxtop}$。当务之急便是确认在两人足够聪明的情况下，$x$ 是多少，这样便能记忆化搜索了。

考虑如下问题：

有一个类似帕斯卡三角形的图案，第 $i$ 层有 $i$ 个顶点（记作 $(i, 1), (i, 2), \dots, (i, i)$），两人交替从顶点往下走，每一步可以向左（$(i, j) \to (i + 1, j)$）或者向右（$(i, j) \to (i + 1, j + 1)$），总共走 $t$ 步，第 $t$ 层的节点有权值，一个人想最大化终点的权值，一个人想最小化。问两人的策略。

我们分类讨论：

• $t$ 是偶数，则后手通过每一步与先手相反的方法，必定可以选到 $(t + 1, \frac{t}{2} + 1)$。此外还可以选到 $(t + 1, \frac{t}{2})$ 和 $(t + 1, \frac{t}{2} + 2)$ 中对自己来说较劣的一个结果；
• $t$ 是奇数，则后手通过同样的方法可以限制先手只能选到 $(t + 1, \frac{t + 1}{2})$ 和 $(t + 1, \frac{t + 1}{2} + 1)$ 中对先手较优的结果。

简单讨论一下可以证明这个结论的充要性，此处略去。

那么一个状态最多扩展出三个状态，且三个状态后续的扩展有重叠，最多扩展 $O(\log n)$ 轮（两次扩展总数减半），总复杂度是一个关于 $\log n$ 的多项式，可以通过。

写法参考了出题人的代码。

 /* NE_Cat 4.1 */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

int T; long long n;

map < tuple < long long, long long, bool >, long long > f;
inline long long work(long long i, long long j, bool op)
{
	if(!i && !j) return 0;
	if(f.count(make_tuple(i, j, op))) return f[make_tuple(i, j, op)];
	if(i <= 1) return f[make_tuple(i, j, op)] = work(j, 0, op);
	long long t = i / 2; int nxt_op = op ^ (t & 1);
	if(op == false)
	{
		if(t % 2 == 1) return f[make_tuple(i, j, op)] = t + min(work(j + t / 2 + 1, t / 2, nxt_op), work(j + t / 2, t / 2 + 1, nxt_op));
		else return f[make_tuple(i, j, op)] = t + max(work(j + t / 2, t / 2, nxt_op), min(work(j + t / 2 - 1, t / 2 + 1, nxt_op), work(j + t / 2 + 1, t / 2 - 1, nxt_op)));
	}
	else
	{
		if(t % 2 == 1) return f[make_tuple(i, j, op)] = t + max(work(j + t / 2 + 1, t / 2, nxt_op), work(j + t / 2, t / 2 + 1, nxt_op));
		else return f[make_tuple(i, j, op)] = t + min(work(j + t / 2, t / 2, nxt_op), max(work(j + t / 2 - 1, t / 2 + 1, nxt_op), work(j + t / 2 + 1, t / 2 - 1, nxt_op)));
	}
}

inline void sol()
{
	cin >> n;
	cout << work(n, 0, 0) << '\n';
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while(T--) sol();
	return 0;
}
/*

*/