# [Solution] Game of Pooks solution codechef

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 1iN1≤i≤N
• (x,i)(x,i) for every 1iN1≤i≤N
• (x+1,y1)(x+1,y−1), if x<Nx<N and y2y≥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

• 1T1051≤T≤105
• 1N1091≤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.