Problem Description

In an intellectual board game, two players, Xiao Lan and Xiao Qiao, need to operate on an $n \times n$ matrix whose initial values are all $0$, in order to show their wisdom and strategy and determine who is the strongest strategist.

The rules are as follows:

• Xiao Lan moves first. After he finishes his move, it is Xiao Qiao’s turn, then Xiao Lan’s turn again, and so on alternately.
• On each of Xiao Lan’s turns, he can choose $2$ elements in the matrix and change the values of these elements to $1$.
• On Xiao Qiao’s $1$-st turn, he can choose a $1 \times 1$ submatrix and reset all elements in that submatrix to $0$. On Xiao Qiao’s $2$-nd turn, he can choose a $2 \times 2$ submatrix and reset all elements in that submatrix to $0$. By analogy, on Xiao Qiao’s $i$-th turn, he can choose an $i \times i$ submatrix and reset all elements in that submatrix to $0$.
• After both sides have each made $n$ moves, the game ends.

Let $X$ be the maximum number of elements with value $1$ that ever appears during the entire game.

Xiao Lan tries to maximize $X$, while Xiao Qiao tries to minimize $X$.

Assuming both players have perfect logical reasoning ability and always take the best strategy, what will $X$ be (that is, what is the maximum number of elements with value $1$ during the whole game)?

Input Format

The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain an integer $n$, representing the size of the matrix.

Output Format

For each test case, output one line containing an integer, representing the answer.

2
2
5

3
5

Hint

[Sample Explanation]

In the first sample, Xiao Lan and Xiao Qiao take turns operating on a $2 \times 2$ matrix.

Initial matrix state:

Xiao Lan’s 1st turn: Change two elements with value $0$ to $1$. A possible state is:

Xiao Qiao’s 1st turn: Xiao Qiao can only choose a $1 \times 1$ submatrix to reset the element to $0$. In order to minimize the number of elements with value $1$, Xiao Qiao needs to reset one element that is already $1$ to $0$. A possible state is:

Xiao Lan’s 2nd turn: Xiao Lan again changes two elements with value $0$ to $1$. A possible state is:

Xiao Qiao’s 2nd turn: Xiao Qiao can choose a $2 \times 2$ submatrix (that is, the whole matrix) and reset all values to $0$.

Therefore, when both sides use the best strategy, the maximum number of elements with value $1$ in the matrix can reach $3$.

[Constraints and Notes for Testcases]

For $30\%$ of the test cases, $1 \le T \le 10^3$, $1 \le n \le 10^3$.
For all test cases, $1 \le T \le 10^5$, $1 \le n \le 10^9$.

Translated by ChatGPT 5