Game of Pooks Solution codechef

We have found a new chess character — pook. It has the qualities of both a rook and a pawn. Specifically, treating the chessboard to be an $N \times N$ grid where $(i, j)$ denotes the intersection of the $i$ -th row and the $j$ -th column, a pook placed at square $(x, y)$ threatens the following squares:

$(i, y)$ for every $1 \leq i \leq N$
$(x, i)$ for every $1 \leq i \leq N$
$(x + 1, y - 1)$ , if $x < N$ and $y \geq 2$
$(x + 1, y + 1)$ , if $x < N$ and $y < N$

Find the maximum number of pooks that can be placed on an empty $N \times N$ chessboard such that none of them threaten each other.

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases. Then the test cases follow.
Each test case consists of a single line of input, containing a single integer $N$ .

Output Format

For each test case, output in a single line the maximum number of pooks that can be placed on the chessboard such that they don’t threaten each other.

Constraints

$1 \leq T \leq 10^{5}$
$1 \leq N \leq 10^{9}$

Sample Input 1

Sample Output 1

1
1
2

Explanation

Test case $1$ : There is a single square, so we have a single pook.

Test case $2$ : We can only place one pook. No matter where the first is placed, placing a second will lead to one of the two being threatened.

Test case $3$ : Placing $2$ pooks on a $3 \times 3$ grid is easy — for example, place one at $(1, 2)$ and another at $(3, 3)$ . It can be shown that placing three is not possible.