P10582 [蓝桥杯 2024 国 A] 最强策略家

在一场智力对弈的游戏中，两位玩家小蓝和小乔需要对一个初始值均为 $0$、大小为 $n \times n$ 的矩阵进行操作，以展现他们的智慧和谋略，并确定谁才是最强的策略家。 操作规则如下： - 小蓝拥有先手操作权，完成操作后轮到小乔，然后再轮到小蓝，依此规律交替进行。 - 在小蓝的每个回合中，他可以选择矩阵中的 $2$ 个元素，并将这些元素的值变更为 $1$。 - 在小乔的第 $1$ 个回合中，他可以选择一个大小为 $1\times 1$ 的子矩阵，并将该子矩阵内的所有元素的值重置为 $0$。在小乔的第 $2$ 个回合中，他可以选择一个 $2\times 2$ 的子矩阵，并将该子矩阵内的所有元素的值重置为 $0$。以此类推，在小乔的第 $i$ 个回合中，他可以选择一个大小为 $i\times i$ 的子矩阵，并将该子矩阵内所有元素的值重置为 $0$。 - 在双方各进行了 $n$ 次操作后，游戏结束。 设在整个游戏过程中，矩阵中值为 $1$ 的元素的数量最多时为 $X$。 小蓝致力于最大化 $X$ 的值，小乔致力于最小化 $X$ 的值。 假设两位玩家都具有完美的逻辑推理能力，并总是采取最佳策略。请问，$X$ 的值会是多少（即在整个游戏过程中，矩阵中值为 $1$ 的元素的数量最多时是多少）？

输入的第一行包含一个整数 $T$，表示数据的组数。 接下来 $T$ 行，每行包含一个整数 $n$，表示矩阵的大小。

对于每组数据，输出一行包含一个整数，表示答案。

**【样例说明】** 在第一个样例中，小蓝和小乔需要轮流操作一个 $2\times 2$ 的矩阵。 **初始矩阵状态：** $$ \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$ **小蓝的第 $1$ 个回合：** 将两个值为 $0$ 的元素变更为 $1$。可能的状态为： $$ \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} $$ **小乔的第 $1$ 个回合：** 小乔只能选择一个 $1\times 1$ 的子矩阵将元素重置为 $0$。为了最小化值为 $1$ 的元素数量，小乔需要将已经是 $1$ 的一个元素重置为 $0$。可能的状态为： $$ \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} $$ **小蓝的第 $2$ 个回合：** 小蓝再次将两个元素值为 $0$ 的元素变更 $1$。可能的状态为： $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$ **小乔的第 $2$ 个回合：** 小乔可以选择一个 $2\times 2$ 的子矩阵（即整个矩阵），并且把所有值重置为 $0$。 $$ \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$ 因此，在双方都采取最佳策略下，矩阵中值为 $1$ 的元素最多时能达到 $3$ 个。 **【评测用例规模与约定】** 对于 $30\%$ 的评测用例，$1 \le T \le 10^3$，$1 \le n \le 10^3$。 对于所有评测用例，$1 \le T \le 10^5$，$1 \le n \le 10^9$。