题目描述

在一场智力对弈的游戏中，两位玩家小蓝和小乔需要对一个初始值均为 ~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~，表示矩阵的大小。

输出格式

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

输入输出样例 #1

输入 #1

2
2
5

输出 #1

3
5

说明/提示

【样例说明】

在第一个样例中，小蓝和小乔需要轮流操作一个 ~2\times 2~ 的矩阵。

初始矩阵状态：

$$\displaystyle \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$

小蓝的第 ~1~ 个回合： 将两个值为 ~0~ 的元素变更为 ~1~。可能的状态为：

$$\displaystyle \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} $$

小乔的第 ~1~ 个回合： 小乔只能选择一个 ~1\times 1~ 的子矩阵将元素重置为 ~0~。为了最小化值为 ~1~ 的元素数量，小乔需要将已经是 ~1~ 的一个元素重置为 ~0~。可能的状态为：

$$\displaystyle \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} $$

小蓝的第 ~2~ 个回合： 小蓝再次将两个元素值为 ~0~ 的元素变更 ~1~。可能的状态为：

$$\displaystyle \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$

小乔的第 ~2~ 个回合： 小乔可以选择一个 ~2\times 2~ 的子矩阵（即整个矩阵），并且把所有值重置为 ~0~。

$$\displaystyle \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~。