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

You are given an integer N. Consider the sequence containing the integers 1, 2, \ldots, N in increasing order (each exactly once). Find the maximum length of its contiguous subsequence with an even sum.

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

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a single integer N.

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

For each test case, print a single line containing one integer --- the maximum length of a contiguous subsequence with even sum.

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

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{4}$

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3
3
4
5
----- Sample Output 1 ------ 
3
4
4
----- explanation 1 ------ 
Example case 1: The optimal choice is to choose the entire sequence, since the sum of all its elements is $1 + 2 + 3 = 6$, which is even.

Example case 3: One of the optimal choices is to choose the subsequence $[1, 2, 3, 4]$, which has an even sum.

Source: codechef | Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Ad-hoc


Solutions:
for i in range(int(input())):
	n = int(input())
	c = n * (n + 1) // 2
	if c % 2 == 0:
		print(n)
	else:
		print(n - 1)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	print(n - 1 if n * (n + 1) // 2 & 1 else n)


n = int(input())
for _ in range(n):
	n = int(input())
	sum = n * (n + 1) / 2
	if sum % 2 == 0:
		print(n)
	else:
		print(n - 1)


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


import math
t = int(input())
for _ in range(t):
	n = int(input())
	x = n * (n + 1) / 2
	if x % 2 == 0:
		print(n)
	else:
		print(n - 1)


for i in range(int(input())):
	a = int(input())
	if a * (a + 1) % 4 == 0:
		print(a)
	else:
		print(a - 1)


for i in range(int(input())):
	n = int(input())
	a = n - n // 2
	if a & 1:
		print(n - 1)
	else:
		print(n)


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


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n * (n + 1) % 4 == 0:
		print(n)
	else:
		print(n - 1)


for _ in range(int(input())):
	n = int(input())
	print(n - 1 if len([x for x in range(1, n + 1, 2)]) % 2 != 0 else n)


for _ in range(int(input())):
	buddyluuu = int(input())
	kanna = buddyluuu * (buddyluuu + 1) / 2
	if kanna % 2 == 0:
		print(buddyluuu)
	else:
		print(buddyluuu - 1)


l = []
t = int(input())
for r in range(t):
	n = int(input())
	sumo = n * (n + 1) / 2
	if sumo % 2 == 0:
		print(n)
	else:
		print(n - 1)


T = int(input())
for _ in range(T):
	N = int(input())
	sum = N * (N + 1) / 2
	if sum % 2 == 0:
		print(N)
	else:
		print(N - 1)


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = [aim for aim in range(1, wife + 1)]
	if sum(life) % 2 == 0:
		print(wife)
	else:
		print(wife - 1)


for i in range(int(input())):
	N = int(input())
	l = [i for i in range(1, N + 1)]
	if sum(l) % 2 == 0:
		print(N)
	else:
		print(N - 1)


t = int(input())
sum = 0
for i in range(t):
	n = int(input())
	sum = n * (n + 1) / 2
	if sum % 2 != 0:
		print(n - 1)
	elif sum % 2 == 0:
		print(n)


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


t = int(input())
for i in range(t):
	b = int(input())
	a = b / 2 * (2 + (b - 1))
	if a % 2 == 0:
		print(b)
	else:
		print(b - 1)


t = int(input())
for i in range(t):
	N = int(input())
	s = N * (N + 1) // 2
	if s % 2 == 0:
		print(N)
	else:
		print(N - 1)


T = int(input())
for i in range(T):
	n = int(input())
	sum = n * (n + 1) / 2
	if sum % 2 == 0:
		print(n)
	else:
		print(n - 1)


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


for _ in range(int(input())):
	n = int(input())
	e = int(n / 2)
	o = n - e
	if o % 2 != 0:
		f = o - 1
	else:
		f = o
	print(e + f)


def f(n):
	return int(n / 2 * (n + 1))
for _ in range(int(input())):
	x = int(input())
	if f(x) % 2 == 0:
		print(x)
	else:
		print(x - 1)


for _ in range(int(input())):
	n = int(input())
	even = n // 2
	odd = abs(even - n)
	if odd % 2 == 0:
		print(n)
	else:
		print(n - 1)


for _ in range(int(input())):
	x = int(input())
	summa = x * (x + 1) / 2
	if summa % 2 == 0:
		print(x)
	else:
		print(x - 1)


cases = int(input())
for _ in range(cases):
	n = int(input())
	ans = n * (n + 1) / 2
	if ans % 2 == 0:
		print(n)
	else:
		print(n - 1)


for _ in range(int(input())):
	N = int(input())
	Sum = N * (N + 1) // 2
	if Sum % 2 != 0:
		print(N - 1)
	else:
		print(N)


for i in range(int(input())):
	x = int(input())
	s = x * (x + 1) / 2
	if s % 2 == 0:
		print(x)
	else:
		print(x - 1)


for i in range(int(input())):
	n = int(input())
	count = 0
	summa = n * (n + 1) / 2
	if summa % 2 == 0:
		print(n)
	else:
		print(n - 1)


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


for _ in range(int(input())):
	a = int(input())
	s = a * (a + 1) / 2
	if s % 2 == 0:
		print(a)
	else:
		print(a - 1)


for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(1)
	elif n % 4 == 0:
		print(n)
	elif n % 4 == 3:
		print(n)
	elif n % 4 == 2:
		print(n - 1)
	else:
		print(n // 4 * 4)


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


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


try:
	for i in range(int(input())):
		n = int(input())
		if n * (n + 1) // 2 % 2 == 0:
			print(n)
		else:
			print(n - 1)
except Exception as e:
	print(e)


t = int(input())
while t > 0:
	n = int(input())
	sumOfN = lambda x: x * (x + 1) / 2
	if sumOfN(n) % 2 == 0:
		print(n)
	else:
		print(n - 1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	seq_sum = n * (n + 1) // 2
	if seq_sum % 2 == 0:
		max_len = n
	else:
		max_len = n - 1
	print(max_len)


ty = int(input())
yu = []
for l in range(0, ty):
	p = int(input())
	yu.append(p)
for nn in yu:
	ip = nn * (nn + 1) // 2
	if ip % 2 == 0:
		print(nn)
	else:
		print(nn - 1)


x = int(input())
for t in range(x):
	n = int(input())
	sum = n * (n + 1) / 2
	if sum % 2 == 0:
		print(n)
	else:
		print(n - 1)


t = int(input())
for i in range(t):
	n = int(input())
	lst = [i for i in range(1, n + 1)]
	sum = n * (n + 1) // 2
	if sum % 2 == 0:
		print(n)
	else:
		print(n - 1)