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

## [Solution] Game of Pooks solution codechef

- (i,y)(i,y) for every 1≤i≤N1≤i≤N
- (x,i)(x,i) for every 1≤i≤N1≤i≤N
- (x+1,y−1)(x+1,y−1), if x<Nx<N and y≥2y≥2
- (x+1,y+1)(x+1,y+1), if x<Nx<N and y<Ny<N

Find the **maximum** number of pooks that can be placed on an empty N×NN×N chessboard such that none of them threaten each other.

### Input Format

- The first line of input will contain a single integer TT, 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 NN.

### 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.

## [Solution] Game of Pooks solution codechef

- 1≤T≤1051≤T≤105
- 1≤N≤1091≤N≤109

### Sample Input 1

```
3
1
2
3
```

### Sample Output 1

```
1
1
2
```

## Game of Pooks solution Explanation

**Test case 11:** There is a single square, so we have a single pook.

**Test case 22:** 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 33:** Placing 22 pooks on a 3×33×3 grid is easy — for example, place one at (1,2)(1,2) and another at (3,3)(3,3). It can be shown that placing three is not possible.