## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Game of Pooks CodeChef Solution | CodeChef Problem Solution 2022

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×N$ grid where $\left(i,j\right)$ denotes the intersection of the $i$-th row and the $j$-th column, a pook placed at square $\left(x,y\right)$ threatens the following squares:

• $\left(i,y\right)$ for every $1\le i\le N$
• $\left(x,i\right)$ for every $1\le i\le N$
• $\left(x+1,y-1\right)$, if $x and $y\ge 2$
• $\left(x+1,y+1\right)$, if $x and $y

Find the maximum number of pooks that can be placed on an empty $N×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\le T\le {10}^{5}$
• $1\le N\le {10}^{9}$

### Sample Input 1

3
1
2
3


### 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×3$ grid is easy — for example, place one at $\left(1,2\right)$ and another at $\left(3,3\right)$. It can be shown that placing three is not possible.