题目描述

在一场智力对弈的游戏中，两位玩家小蓝和小乔需要对一个初始值均为 $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
2
5

3
5

提示

【样例说明】

在第一个样例中，小蓝和小乔需要轮流操作一个 $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$。