#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/15/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Corner Meeting - Repovive Starter Round 4 | Repovive | Repovive

15C. Corner Meeting

1500 pts1s256 MB

The board contains all cells $(x,y)$ such that $0 \le x,y \le n$ .

Piece $A$ starts at cell $(0,0)$ , and piece $B$ starts at cell $(n,n)$ .

In one move, both pieces act simultaneously.

Piece $A$ may stay in its current cell or move to a cell that shares a side with its current cell.
Piece $B$ may stay in its current cell or move to a cell that shares exactly one corner with its current cell.

A piece may never leave the board.

For each test case, find the minimum number of moves after which it is possible for both pieces to be on the same cell.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 10^9$

Input

t

\left. \begin{array}{l} n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Case 4

Explanation

Case 1

After one move, piece A can stay at $(0,0)$ , and piece B can move diagonally from $(1,1)$ to $(0,0)$ .

Case 2

After two moves, piece A can stay at $(0,0)$ , and piece B can move diagonally from $(2,2)$ to $(0,0)$ .

Case 3

Both pieces can be at $(1,1)$ after two moves. Piece A reaches it using two side moves, and piece B reaches it using two diagonal moves.

Case 4

Both pieces can be at $(1,1)$ after four moves. Piece A reaches it in two side moves and may stay for the remaining moves, while piece B reaches it using four diagonal moves.

Output

Case 1

Case 2

Case 3

Case 4

The board contains all cells $(x,y)$ such that $0 \le x,y \le n$ .

Piece $A$ starts at cell $(0,0)$ , and piece $B$ starts at cell $(n,n)$ .

In one move, both pieces act simultaneously.

Piece $A$ may stay in its current cell or move to a cell that shares a side with its current cell.
Piece $B$ may stay in its current cell or move to a cell that shares exactly one corner with its current cell.

A piece may never leave the board.

For each test case, find the minimum number of moves after which it is possible for both pieces to be on the same cell.

$1 \le t \le 10^4$
$1 \le n \le 10^9$

t

\left. \begin{array}{l} n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

After one move, piece A can stay at $(0,0)$ , and piece B can move diagonally from $(1,1)$ to $(0,0)$ .

After two moves, piece A can stay at $(0,0)$ , and piece B can move diagonally from $(2,2)$ to $(0,0)$ .

Both pieces can be at $(1,1)$ after two moves. Piece A reaches it using two side moves, and piece B reaches it using two diagonal moves.

Both pieces can be at $(1,1)$ after four moves. Piece A reaches it in two side moves and may stay for the remaining moves, while piece B reaches it using four diagonal moves.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

15C. Corner Meeting

Constraints

Input

Output

Samples

15C. Corner Meeting

Constraints

Input

Output

Samples