Read problem statements in [Mandarin], [Vietnamese], and [Russian] as well.

Chef loves Chess and has thus invented a new piece named "Disabled King".

Let's denote the cell at the intersection of the i-th column from the left and j-th row from the top by (i, j).

If he is currently in cell (x,y), the disabled king can move to the following positions in one move (provided that he remains in the chessboard): 

(x,y+1)
(x,y-1)
(x+1,y+1)
(x+1,y-1)
(x-1,y+1)
(x-1,y-1)

In short, the Disabled King cannot move horizontally.

In an N \times N chessboard, the Disabled King is currently situated at the top-left corner (cell (1, 1)) and wants to reach the top-right corner (cell (N, 1)). Determine the minimum number of moves in which the task can be accomplished.

------ Input Format ------ 

- The first line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single integer N in a separate line.

------ Output Format ------ 

Output the minimum number of moves to get from the top-left cell to the top-right one.

------ Constraints ------ 

$1 ≤ T ≤ 500$
$2 ≤ N ≤ 500$

----- Sample Input 1 ------ 
2
2
3

----- Sample Output 1 ------ 
2
2

----- explanation 1 ------ 
Test case 1:

Initially chef is at $(1, 1)$. He cannot directly move to $(2, 1)$ as the disabled king cannot move horizontally. So he needs at least $2$ moves to reach $(2, 1)$. And that can be achieved by first moving to $(1, 2)$ and then moving to $(2, 1)$ from there.

Test case 2:

Clearly we cannot reach $(3, 1)$ from $(1, 1)$ in just one move. We require at least $2$ moves. And this can be achieved by first moving to $(2, 2)$ and then moving to $(3, 1)$ from there.

Source: codechef | Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc


Solutions:
for i in range(int(input())):
	a = int(input())
	if a % 2 == 0:
		print(a)
	else:
		print(a - 1)


for _ in range(int(input())):
	N = int(input())
	if N % 2 == 0:
		print(N)
	else:
		print(N - 1)


t = int(input())
for i in range(t):
	n = int(input())
	print(2 * (n // 2))


for _ in range(int(input())):
	n = int(input())
	print(n // 2 * 2)


T = int(input())
for cases in range(T):
	N = int(input())
	print(N - N % 2)


T = int(input())
for i in range(T):
	N = int(input())
	if N % 2 == 0:
		print(N)
	else:
		print(N - 1)


import math
for i in range(0, int(input())):
	x = int(input())
	if x % 2 == 0:
		print(x)
	else:
		print(x - 1)


for tc in range(int(input())):
	n = int(input())
	print(2 * (n // 2))


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


t = int(input())
for tc in range(t):
	n = int(input())
	if n % 2 == 0:
		print(n)
	else:
		print(n - 1)


n = int(input())
for i in range(n):
	a = int(input())
	if a == 1:
		print('0')
	elif a % 2 == 0:
		print(a)
	elif a % 2 == 1:
		print(a - 1)


t = int(input())
tt = []
for mm in range(0, t):
	pr = int(input())
	tt.append(pr)
for jj in tt:
	if jj % 2 == 0:
		ipu = jj // 2 + 1
		print(ipu - 1 + jj - ipu + 1)
	else:
		op = (jj + 1) // 2
		print(2 * (op - 1))


n = int(input())
while n > 0:
	x = int(input())
	if x % 2 == 0:
		print(x)
	else:
		print(x - 1)
	n = n - 1


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 1:
		print(n - 1)
	else:
		print(n)


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		if N % 2:
			print(N - 1)
		else:
			print(N)
main()


for _ in range(int(input())):
	n = int(input())
	c = 0
	for i in range(1, n, 2):
		c += 2
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	move = 0
	if n % 2 == 0:
		print(n)
	else:
		print(n - 1)


for _ in range(int(input())):
	n = int(input())
	print(n - (n & 1))


t = int(input())
while t > 0:
	n = int(input())
	if n % 2 == 0:
		print(n)
	else:
		print(n - 1)
	t -= 1


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	n = IN()
	print(n - 1 if n & 1 else n)


times = int(input())
for _ in range(times):
	N = int(input())
	if N % 2 == 0:
		print(N)
	elif N % 2 == 1:
		print(N - 1)


T = int(input())
for x in range(T):
	n = int(input())
	if n % 2 == 0:
		print(n)
	else:
		print(n - 1)


for o in range(int(input())):
	n = int(input())
	if n < 4:
		print('2')
	elif n % 2 == 0:
		print(n)
	else:
		print(n - 1)


import math
for i in range(int(input())):
	n = int(input())
	res = math.ceil((n - 1) / 2) * 2
	print(res)


for I in range(int(input())):
	a = int(input())
	if a % 2:
		print(a - 1)
	else:
		print(a)


import math
(t, i) = (int(input()), 1)
while i <= t:
	n = int(input())
	print(math.floor(n / 2) * 2)
	i += 1