P10582 [Lanquiao Cup 2024 National A] The Strongest Strategist

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)?

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.

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

**[Sample Explanation]** In the first sample, Xiao Lan and Xiao Qiao take turns operating on a $2 \times 2$ matrix. **Initial matrix state:** $$ \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$ **Xiao Lan’s 1st turn:** Change two elements with value $0$ to $1$. A possible state is: $$ \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} $$ **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: $$ \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} $$ **Xiao Lan’s 2nd turn:** Xiao Lan again changes two elements with value $0$ to $1$. A possible state is: $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$ **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$. $$ \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$ 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