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 ≤ i ≤ N
(x, i) for every 1 ≤ i ≤ N
(x+1, y-1), if x < N and y ≥ 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 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
1
1
2
----- explanation 1 ------ 
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.

Difficulty: EASY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	print(n if n > 3 else n - 1 if n > 1 else 1)


t = int(input())
for i in range(t):
	n = int(input())
	print(n if n > 3 else n - 1 if n > 1 else 1)


s = int(input())
for i in range(s):
	a = int(input())
	if a == 2 or a == 3:
		print(a - 1)
	else:
		print(a)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1 or n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		print(n)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(n)
	elif n < 4:
		print(n - 1)
	else:
		print(n)


goals = int(input())
for distractions in range(goals):
	life = int(input())
	print(life if life > 3 else life - 1 if life > 1 else 1)


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n > 1 and n <= 3:
		print(n - 1)
	else:
		print(n)


for i in range(int(input())):
	n = int(input())
	if n != 1 and n < 4:
		print(n - 1)
	else:
		print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	if n < 4 and n != 1:
		print(n - 1)
	else:
		print(n)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	if n < 4 and n != 1:
		print(n - 1)
	else:
		print(n)


import math as m
for i in range(int(input())):
	n = int(input())
	print(n if n > 3 else n - 1 if n > 1 else 1)


for _ in range(int(input())):
	N = int(input())
	if N != 1 and N < 4:
		print(N - 1)
	else:
		print(N)


import math

def solve():
	if n < 4 and n != 1:
		return n - 1
	else:
		return n
for _ in range(int(input())):
	n = int(input())
	print(solve())


T = int(input())
for _ in range(T):
	n = int(input())
	if n == 2 or n == 3:
		print(n - 1)
	else:
		print(n)


t = int(input())
for it in range(t):
	n = int(input())
	if n > 3:
		print(n)
	else:
		print((n + 1) // 2)


for _ in range(int(input())):
	a = int(input())
	if a == 2 or a == 3:
		print(a - 1)
	else:
		print(a)


for _ in range(int(input())):
	ans = [1, 1, 2, 3]
	n = int(input())
	if n < 4:
		print(ans[n - 1])
	else:
		print(n)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	if n == 1 or n == 2:
		sys.stdout.write('1\n')
	elif n == 3:
		sys.stdout.write('2\n')
	else:
		sys.stdout.write(str(n) + '\n')


t = int(input())
for i in range(t):
	N = int(input())
	if N == 1:
		print('1')
	elif N <= 3:
		print(N - 1)
	else:
		print(N)


X = int(input())
for i in range(X):
	Y = int(input())
	if Y == 2 or Y == 3:
		print(Y - 1)
	else:
		print(Y)


t = int(input())
while t != 0:
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2 or n == 3:
		print(n - 1)
	else:
		print(n)
	t -= 1


t = int(input())
while t:
	n = int(input())
	if n == 1:
		print('1')
	elif n >= 2 and n <= 3:
		print(n - 1)
	else:
		print(n)
	t -= 1


for i in range(int(input())):
	N = int(input())
	if N <= 3:
		print(max(1, N - 1))
	else:
		print(N)


for tc in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2 or n == 3:
		print(n - 1)
	else:
		print(n)