Chef has a binary array A of length N. In one operation, Chef does the following:

1. Select any L and R such that (1 ≤ L < R ≤ |A|) \\
2. Add A_{L} \oplus A_{L+1} \oplus \ldots \oplus A_{R} to his *score* (Here, \oplus denotes the [bitwise XOR operation] \\
3. Remove the subarray A_{L \dots R} from A 

Determine the maximum score Chef can get after performing the above operation any number of times.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the maximum score Chef can get.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$A_{i} \in \{0, 1\}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
5
1 0 0 0 1
3
1 1 1
3
0 0 0

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

----- explanation 1 ------ 
Test Case 1: We can perform the following moves:
- $A = [1, 0, 0, 0, 1]$. Select $L = 1$ and $R = 3$ and remove subarray $[1, 0, 0]$. $A$ becomes $[0, 1]$.
- $A = [0, 1]$. Select $L = 1$ and $R = 2$ and remove subarray $[0, 1]$. $A$ becomes $[]$.

Total score $= 1 + 1 = 2$

Test Case 2: We can perform the following move:
- $A = [1, 1, 1]$. Select $L = 1$ and $R = 3$ and remove subarray $[1, 1, 1]$. $A$ becomes $[]$.

Total score $= 1$

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(start, cnt, ones, zeros) = (0, 0, 0, 0)
	n = int(input())
	arr = list(map(str, input().split()))
	for i in arr:
		if i == '0':
			zeros += 1
		else:
			ones += 1
	print(min(ones, zeros) + max(0, ones - zeros) // 3)


import math

def Solve(a, n):
	stack = [a[0]]
	score = 0
	for i in a[1:]:
		if len(stack) != 0 and stack[-1] != i:
			score += 1
			stack.pop()
		else:
			stack.append(i)
	temp = 0
	if stack.count(1) == len(stack):
		score = score + len(stack) // 3
	return score + temp
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(Solve(a, n))


t = int(input())

def fun(st):
	st = st.replace(' ', '')
	count = 0
	while len(st) > 3:
		flag = 0
		if '01' in st:
			st = st.replace('01', '', 1)
			count += 1
			flag += 1
		if '10' in st:
			st = st.replace('10', '', 1)
			count += 1
			flag += 1
		if flag == 0:
			break
	if '0' in st and '1' in st:
		count += 1
	elif '1' in st:
		count += len(st) // 3
	print(count)
for _ in range(t):
	n = int(input())
	st = input()
	st = st.replace(' ', '')
	fun(st)


for _ in range(int(input())):
	K = int(input())
	A = list(map(int, input().split()))
	c0 = 0
	c1 = 0
	for i in range(K):
		if A[i] == 0:
			c0 += 1
		else:
			c1 += 1
	if c0 >= c1:
		print(c1)
	else:
		ans = c0
		x = c1 - c0
		print(ans + x // 3)


t = int(input())
from collections import Counter
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = Counter(arr)
	tmp = min(cnt[0], cnt[1])
	if cnt[1] > cnt[0]:
		res = cnt[1] - cnt[0]
		print(tmp + res // 3)
	else:
		print(tmp)


for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	(C0, C1) = (0, 0)
	for i in range(N):
		if A[i] == 0:
			C0 += 1
		else:
			C1 += 1
	if C1 == 0:
		print(0)
	elif C0 == 0:
		print(int(C1 / 3))
	elif C0 >= C1:
		print(C1)
	else:
		print(C0 + int((C1 - C0) / 3))


for i in range(int(input())):
	aim = int(input())
	(wife, Life, knife) = (0, 0, 0)
	life = list(map(int, input().split()))
	for death in life:
		wife += death == 0
		Life += death == 1
		temp = min(wife, Life)
		wife -= temp
		Life -= temp
		knife += temp
	print(knife + Life // 3)


t = int(input())
for i in range(t):
	n = int(input())
	lst = [int(x) for x in input().split()]
	if lst.count(1) == 0:
		print(0)
	else:
		one = lst.count(1)
		zero = lst.count(0)
		ans = min(one, zero) + max(0, one - zero) / 3
		print(int(ans))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = min(l.count(0), l.count(1))
	x = max(l.count(1) - l.count(0), 0)
	ans += x // 3
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = []
	c = 0
	for i in l:
		if s == []:
			s.append(i)
		elif i != s[-1]:
			c += 1
			s.pop()
		else:
			s.append(i)
	while len(s) > 1:
		top = s[-1]
		s.pop(-1)
		if top == s[-1]:
			s.pop()
			s.append(0)
		else:
			c += 1
			s.pop()
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	(x, y, z) = (0, 0, 0)
	m = list(map(int, input().split()))
	for i in m:
		x += i == 0
		y += i == 1
		temp = min(x, y)
		x -= temp
		y -= temp
		z += temp
	print(z + y // 3)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	l1 = arr.count(1)
	l2 = arr.count(0)
	c = min(l1, l2)
	res = c + max(0, (l1 - l2) // 3)
	print(res)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	(cnto, cntz) = (0, 0)
	for i in li:
		if i == 1:
			cnto += 1
		else:
			cntz += 1
	ans = 0
	common = min(cnto, cntz)
	ans += common
	cnto = cnto - common
	cntz = cntz - common
	ans += cnto // 3
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	zero = l.count(0)
	one = n - zero
	b = 0
	if one > zero:
		b = one - zero
	print(min(one, zero) + b // 3)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(start, cnt, ones, zeros) = (0, 0, 0, 0)
	n = int(input())
	arr = list(map(str, input().split()))
	for i in arr:
		if i == '0':
			zeros += 1
		else:
			ones += 1
	print(min(ones, zeros) + max(0, ones - zeros) // 3)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = sum(l)
	val = min(x, n - x)
	val += (x - val) // 3
	print(val)


for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ones = 0
	zeros = 0
	count = 0
	for i in arr:
		if i == 0:
			zeros += 1
		else:
			ones += 1
	if ones >= zeros:
		count = zeros
		ones = ones - zeros
		zeros = 0
	else:
		count = ones
		ones = 0
	count += ones // 3
	print(count)


for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split())).count(1)
	val = min(a, n - a)
	val += (a - val) // 3
	print(val)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	zc = 0
	oc = 0
	pc = 0
	for i in a:
		zc += i == 0
		oc += i == 1
	te = min(zc, oc)
	zc -= te
	oc -= te
	pc += te
	print(pc + oc // 3)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	one = A.count(1)
	zero = n - one
	if zero >= one:
		print(one)
	else:
		print(zero + (one - zero) // 3)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	stack = []
	c = 0
	for i in range(n):
		if stack == []:
			stack.append(a[i])
		elif a[i] != stack[-1]:
			c += 1
			stack.pop(-1)
		else:
			stack.append(a[i])
	while len(stack) > 1:
		t = stack[-1]
		stack.pop(-1)
		if t == stack[-1]:
			stack.pop(-1)
			stack.append(0)
		else:
			c += 1
			stack.pop(-1)
	print(c)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	ones = L.count(1)
	zeros = L.count(0)
	if ones >= zeros:
		print(zeros + (ones - zeros) // 3)
	else:
		print(ones)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	ans = 0
	zeros_available = 0
	ones_available = 0
	for val in L:
		if val == 0:
			if ones_available:
				ans += 1
				ones_available -= 1
			else:
				zeros_available += 1
		elif zeros_available:
			ans += 1
			zeros_available -= 1
		else:
			ones_available += 1
	ans += ones_available // 3
	print(ans)


def score(n, arr):
	stack = []
	i = 0
	res = 0
	while i < len(arr):
		if len(stack) == 0:
			if arr[i] == 0:
				stack.append(0)
			else:
				stack.append(1)
		elif arr[i] == 0:
			if stack[-1] == 1:
				stack.pop()
				res += 1
			else:
				stack.append(0)
		elif stack[-1] == 0:
			stack.pop()
			res += 1
		else:
			stack.append(1)
		i += 1
	if len(stack) > 0 and stack[-1] == 0:
		return res
	if len(stack) > 0:
		res += len(stack) // 3
	return res
case = int(input())
for i in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ans = score(n, arr)
	print(ans)


T = int(input())
for x in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	o = a.count(1)
	z = a.count(0)
	if z >= o:
		print(o)
	else:
		print(z + (o - z) // 3)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	one = a.count(1)
	zero = a.count(0)
	if zero >= one:
		print(one)
	else:
		print(zero + (one - zero) // 3)


for _ in range(int(input())):
	l = int(input())
	s = input().split(' ')
	z = 0
	o = 0
	for k in range(l):
		if s[k] == '1':
			o += 1
		else:
			z += 1
	if z >= o:
		print(o)
	else:
		print(z + (o - z) // 3)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	one = a.count(1)
	zero = a.count(0)
	ans = min(one, zero)
	one -= ans
	zero -= ans
	one = max(one, one - zero)
	print(ans + one // 3)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(input())
	ones = l.count('1')
	zeroes = l.count('0')
	if ones <= zeroes:
		print(ones)
	else:
		print(zeroes + (ones - zeroes) // 3)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = []
	count = 0
	for i in l:
		if len(s) == 0 or i == s[0]:
			s.append(i)
		else:
			s.pop(-1)
			count += 1
	if len(s) and s[0] == 1:
		count += len(s) // 3
	print(count)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	(z, o) = (0, 0)
	for i in range(n):
		if x[i] == 0:
			z += 1
		elif x[i] == 1:
			o += 1
	if o <= z:
		print(o)
	elif o > z:
		print(z + (o - z) // 3)


for t in range(int(input())):
	n = int(input())
	lst = [int(i) for i in input().split()]
	res = 0
	ones = lst.count(1)
	zeros = lst.count(0)
	res += min(zeros, ones)
	ones -= min(ones, zeros)
	res += ones // 3
	print(res)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	a = input()
	z = a.count('0')
	o = a.count('1')
	if z >= o:
		print(o)
	else:
		print(z + (o - z) // 3)


def subarray_removal(arr):
	num_zeroes = 0
	num_ones = 0
	for i in arr:
		if i == 1:
			num_ones += 1
		else:
			num_zeroes += 1
	m = min(num_zeroes, num_ones)
	if num_zeroes > num_ones:
		return num_ones
	else:
		return num_zeroes + (num_ones - num_zeroes) // 3
t = int(input())
for _ in range(t):
	unused_n = input()
	arr = [int(x) for x in input().split()]
	print(subarray_removal(arr))


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ones_count = 0
	zeroes_count = 0
	for j in arr:
		if j == 1:
			ones_count += 1
		else:
			zeroes_count += 1
	minimum = min(ones_count, zeroes_count)
	ans = minimum
	ones_count -= minimum
	if ones_count > 0:
		ans += ones_count // 3
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = input().split().count('1')
	c = n - a
	if a > c:
		print(c + (a - c) // 3)
	else:
		print(a)


import sys

def main():
	next(stdin)
	while (N := next(stdin, None)):
		A = next(stdin)
		zer = A.count('0')
		one = A.count('1')
		print(min(zer, one) + (one - min(zer, one)) // 3)
stdin = sys.stdin
main()


import sys

def main():
	next(stdin)
	for N in stdin:
		A = next(stdin)
		zer = A.count('0')
		one = A.count('1')
		print(min(zer, one) + (one - min(zer, one)) // 3)
stdin = sys.stdin
main()


import sys

def main():
	next(sys.stdin)
	for N in sys.stdin:
		A = next(sys.stdin)
		zer = A.count('0')
		one = A.count('1')
		write(str(min(zer, one) + (one - min(zer, one)) // 3) + '\n')
(read, write, flush) = (sys.stdin.readline, sys.stdout.write, sys.stdout.flush)
main()


import sys

def main():
	for _ in range(int(read().strip())):
		N = int(read().strip())
		A = [int(__) for __ in read().split()]
		zer = A.count(0)
		print(min(zer, N - zer) + (N - zer - min(zer, N - zer)) // 3)
(read, write, flush) = (sys.stdin.readline, sys.stdout.write, sys.stdout.flush)
main()


import sys

def main():
	for _ in range(int(read().strip())):
		N = int(read().strip())
		A = [int(__) for __ in read().split()]
		zer = A.count(0)
		one = A.count(1)
		write(str(min(zer, one) + (one - min(zer, one)) // 3) + '\n')
(read, write, flush) = (sys.stdin.readline, sys.stdout.write, sys.stdout.flush)
main()


for _ in range(int(input())):
	n = int(input())
	c1 = input().split().count('1')
	c0 = n - c1
	if c1 > c0:
		print(c0 + (c1 - c0) // 3)
	else:
		print(c1)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(str, input().split()))
	z = 0
	o = 0
	for i in range(n):
		if lst[i] == '0':
			z += 1
		else:
			o += 1
	k = min(z, o)
	print(k + (o - k) // 3)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	one = l.count(1)
	zero = n - one
	m = min(one, zero)
	sam = m + (one - m) // 3
	print(sam)


for _ in range(int(input())):
	n = int(input())
	a = ''.join(input().split())
	c1 = sum((1 for x in a if x == '1'))
	c0 = n - c1
	if c0 == n:
		print(0)
	elif c1 == n:
		print(c1 // 3)
	else:
		res = min(c1, c0)
		if c1 > c0:
			res += (c1 - res) // 3
		print(res)


T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	c1 = sum((1 for i in L if i == 1))
	c0 = n - c1
	if c0 == n:
		print(0)
	elif c1 == n:
		print(n // 3)
	else:
		pairs = min(c1, c0)
		if c1 > c0:
			pairs += (c1 - c0) // 3
		print(pairs)


for i in range(int(input())):
	N = int(input())
	bin_array = [int(elem) for elem in input().split(' ')]
	zeros = bin_array.count(0)
	ones = bin_array.count(1)
	if zeros >= ones:
		print(ones)
		continue
	print(zeros + (ones - zeros) // 3)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = a.count(0)
	j = a.count(1)
	if i >= j:
		print(j)
	elif j == i + 1:
		print(i)
	else:
		c = j - i
		print(i + c // 3)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	res = 0
	temp = []
	for c in a:
		if len(temp) == 0 or c == temp[-1]:
			temp.append(c)
		else:
			res += 1
			temp.pop()
	if len(temp) > 0 and temp[0] == 1:
		res += len(temp) // 3
	print(res)


T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	ones = L.count(1)
	zeros = N - ones
	if ones == N:
		print(N // 3)
	elif zeros == N:
		print(0)
	else:
		score = min(ones, zeros)
		if zeros < ones:
			score += (ones - zeros) // 3
		print(score)


for _ in range(int(input())):
	n = int(input())
	a = ''.join(input().split())
	count1 = sum((1 for x in a if x == '1'))
	count0 = n - count1
	if count0 == n:
		print(0)
	elif count1 == n:
		print(count1 // 3)
	else:
		npair = min(count1, count0)
		if count1 > count0:
			npair += (count1 - npair) // 3
		print(npair)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count0 = a.count(0)
	count1 = a.count(1)
	result = 0
	if count1 == 0:
		print(0)
	elif count0 == 0:
		print(n // 3)
	else:
		result += min(count0, count1)
		count0 -= result
		count1 -= result
		if count1 == 0:
			print(result)
		else:
			result += count1 // 3
			print(result)


t = int(input())
for i in range(t):
	n = int(input())
	(c1, c2, c3, c4) = (0, 0, 0, 0)
	s = list(map(int, input().split()))
	for x in s:
		if x == 0:
			c1 = c1 + 1
		else:
			c2 = c2 + 1
		c3 = min(c1, c2)
		c1 = c1 - c3
		c2 = c2 - c3
		c4 = c4 + c3
	print(int(c4 + c2 / 3))


mod = 1000000007
from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	c = s.count('1')
	if c <= n // 2:
		print(c)
	else:
		print(s.count('0') + (c - s.count('0')) // 3)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ones = l.count(1)
	zeros = l.count(0)
	m = min(ones, zeros)
	n = n - m - zeros
	print(m + n // 3)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	stack = []
	ans = 0
	for i in range(n):
		if len(stack) == 0 or a[i] == stack[-1]:
			stack.append(a[i])
		else:
			stack.pop()
			ans += 1
	c = 0
	for i in range(len(stack)):
		if stack[i] == 1:
			c += 1
	ans += c // 3
	print(ans)


def main():
	n = int(input())
	s = input().split()
	one_count = 0
	zero_count = 0
	for j in range(len(s)):
		if s[j] == '1':
			one_count += 1
		else:
			zero_count += 1
	res = min(one_count, zero_count)
	temp = n - res - zero_count
	return res + int(temp / 3)
T = int(input())
for i in range(T):
	print(main())


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = min(s.count('0'), s.count('1'))
	x = n - ans - s.count('0')
	if x > 0:
		ans += x // 3
	print(ans)


a = int(input())
for x in range(a):
	k = int(input())
	s = [int(x) for x in input().split(' ')]
	ct = s.count(0)
	pt = s.count(1)
	ans = min(ct, pt)
	pt = max(pt - ct, 0)
	ans += pt // 3
	print(ans)


import os, sys, io, math
from array import array
from math import *
from collections import Counter
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l, i, c) = (IN(), I(), 0, 0)
	(p, t) = (l[0], [])
	for i in l:
		if not t or t[-1] == i:
			t.append(i)
		else:
			t.pop()
			c += 1
	c += t.count(1) // 3
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	bits = list(map(int, input().split(' ')))
	i = 0
	cnt = 0
	prev = bits[0]
	tmp = []
	for x in bits:
		if not tmp or tmp[-1] == x:
			tmp.append(x)
		else:
			tmp.pop()
			cnt += 1
	cnt += tmp.count(1) // 3
	print(cnt)


for i in range(int(input())):
	m = int(input())
	l = list(map(int, input().split()))
	z = l.count(0)
	o = l.count(1)
	ans = min(o, z)
	if o > z:
		ans += (o - z) // 3
		print(ans)
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	x = n - s
	if s <= x:
		print(s)
	else:
		print(x + (s - x) // 3)


for tt in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	s = sum(l)
	k = n - s
	if s <= k:
		print(s)
	else:
		print(k + (s - k) // 3)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ones = l.count(1)
	zeros = l.count(0)
	if zeros >= ones:
		print(ones)
	else:
		print(zeros + (ones - zeros) // 3)


n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	b = l.count(0)
	c = l.count(1)
	z = min(c, b)
	e = z
	d = 0
	if c - b > 2:
		d = (c - z) // 3
	print(e + d)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(z, o) = (0, 0)
	for i in l:
		if i == 1:
			o += 1
		else:
			z += 1
	if o < z:
		z = z - o
		ans = o
	else:
		o = o - z
		ans = z + o // 3
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	one = s.count('1')
	zero = s.count('0')
	if one > zero:
		print(zero + (one - zero) // 3)
	else:
		print(one)


for _ in range(int(input())):
	n = int(input())
	k = sum(list(map(int, input().split())))
	(o, z) = (k, n - k)
	ans = min(o, z)
	o -= ans
	z -= ans
	ans += o // 3
	print(ans)