Alice and Bob are ready to play a new game. Both the players take alternate turns. Alice starts first.  

There are N binary numbers written on a blackboard.  
Alice, in her turn, erases any 2 numbers from the blackboard and writes the [bitwise OR] of those 2 numbers on the blackboard.  
Bob, in his turn, erases any 2 numbers from the blackboard and writes the [bitwise AND] of those 2 numbers on the blackboard.  

Note that, after each move, the count of numbers written on the blackboard reduces by 1. 

Both players play until a single number remains on the blackboard. Alice wants to maximise the remaining number while Bob wants to minimise the remaining number. Find the remaining number if both the players play optimally.

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

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains of a single integer N - the count of numbers written on the blackboard initially.
- Second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots A_{N} - the numbers written on the blackboard.

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

For each test case, output in a single line, the remaining number, if both the players play optimally. 

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 1$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

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

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

----- explanation 1 ------ 
Test case $1$: Alice starts first.
- In the first move, Alice erases $1$ and $0$ and writes $1 | 0 = 1$ on the blackboard. Thus, after this move, the numbers written are $\{1, 1, 1, 1\}$.
- In the second move, Bob erases $1$ and $1$ and writes $1 \& 1 = 1$ on the blackboard. Thus, after this move, the numbers written are $\{1, 1, 1\}$.
- In the third move, Alice erases $1$ and $1$ and writes $1 | 1 = 1$ on the blackboard. Thus, after this move, the numbers written are $\{1, 1\}$.
- In the fourth move, Bob erases $1$ and $1$ and writes $1 \& 1 = 1$ on the blackboard. Thus, after this move, the numbers written are $\{1\}$.

Thus, the remaining number is $1$. 

Test case $2$: It does not matter which two numbers Alice chooses. After the first move, the numbers on the blackboard would be $\{1, 0\}$. Thus, Bob erases these two numbers and writes $1 \& 0= 0$.

Test case $3$: In all the moves, both players erase two $0s$ and write a single $0$. Thus, the remaining element is $0$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics


Solutions:
for test_cases in range(int(input())):
	length = int(input())
	list_a = list(map(int, input().split()))
	count_0 = list_a.count(0)
	count_1 = list_a.count(1)
	if count_1 > count_0 or count_1 == count_0:
		print(1)
	else:
		print(0)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(1) > l.count(0):
		print(1)
	elif l.count(1) < l.count(0):
		print(0)
	else:
		print(1)


for i in range(int(input())):
	n = int(input())
	s = input()
	if s.count('0') <= s.count('1'):
		print(1)
	else:
		print(0)


def func(b):
	t = 0
	i = 0
	while i < len(b):
		if 1 in b and 0 in b:
			if t % 2 == 0:
				b.remove(1)
				b.remove(0)
				b.append(1)
				t = t + 1
			else:
				b.remove(1)
				b.remove(0)
				b.append(0)
				t = t + 1
		else:
			break
		i = i + 1
	while len(b) > 1:
		if t % 2 == 0:
			b.append(b.pop() or b.pop())
			t = t + 1
		else:
			b.append(b.pop() and b.pop())
			t = t + 1
	print(*b, sep='')
a = int(input())
for i in range(a):
	t = int(input())
	b = list(map(int, input().rstrip().split()))
	func(b)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l1 = l.count(1)
	l0 = n - l1
	if l1 > l0:
		print(1)
	elif l0 > l1:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	n = input()
	a = [int(x) for x in input().split()]
	(c0, c1) = (a.count(0), a.count(1))
	print(0 if c0 > c1 else 1)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(1) if lst.count(1) >= lst.count(0) else print(0)


for _ in range(int(input())):
	n = int(input())
	l = input()
	m = l.count('0')
	n = l.count('1')
	if n >= m:
		print(1)
	elif n < m:
		print(0)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	zeros = A.count(0)
	ones = A.count(1)
	if ones >= zeros:
		print(1)
	else:
		print(0)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	z = a.count(0)
	w = a.count(1)
	if w >= z:
		print(1)
	else:
		print(0)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(0) > a.count(1):
		print(0)
	elif a.count(0) < a.count(1):
		print(1)
	elif a.count(0) == a.count(1):
		print(1)


for _ in range(int(input())):
	size = int(input())
	binary = list(map(int, input().split()))
	if binary.count(1) < binary.count(0):
		print(0)
	else:
		print(1)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	zero = a.count(0)
	one = a.count(1)
	pair = min(one, zero)
	count = 0
	i = 0
	while i < pair:
		a.remove(1)
		a.remove(0)
		if count % 2 == 0:
			a.append(1)
		else:
			a.append(0)
			pair += 1
		count += 1
		i += 1
	if a.count(1) == len(a):
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(0) > l.count(1):
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	flag = True
	while flag:
		for i in range(2):
			if 1 in a and 0 in a:
				a.remove(i)
			else:
				a.pop()
			if len(a) == 1:
				flag = False
				break
	print(a[0])


T = int(input())
for _ in range(T):
	N = int(input())
	numbers = list(map(int, input().split(' ')))
	go_on = True
	while go_on:
		for i in range(2):
			numbers.remove(i) if 1 in numbers and 0 in numbers else numbers.pop()
			if len(numbers) == 1:
				go_on = False
				break
	print(numbers[0])


T = int(input())
for _ in range(T):
	N = int(input())
	numbers = list(map(int, input().split(' ')))
	while len(numbers) > 1:
		numbers.remove(0) if 1 in numbers and 0 in numbers else numbers.pop()
		if len(numbers) == 1:
			break
		numbers.remove(1) if 1 in numbers and 0 in numbers else numbers.pop()
	print(numbers[0])


T = int(input())
for i in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(1) >= a.count(0):
		print(1)
	else:
		print(0)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	ones = a.count(1)
	zeros = a.count(0)
	if ones >= zeros:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ones = a.count(1)
	zeros = n - ones
	if min(ones, zeros) == zeros:
		print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	c1 = ar.count(1)
	c0 = ar.count(0)
	if c1 >= c0:
		print(1)
	else:
		print(0)


T = int(input())
for _ in range(T):
	n = int(input())
	blackboard = input().split()
	zeroes = 0
	ones = 0
	for idx in range(n):
		if blackboard[idx] == '0':
			zeroes += 1
		else:
			ones += 1
	if ones >= zeroes:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	print(int(int(input()) <= sum(map(int, input().split())) << 1))


for _ in range(int(input())):
	n = int(input())
	s = sum(map(int, input().split())) << 1
	print(int(n <= s))


vishnesh = int(input())
for vish in range(vishnesh):
	n = int(input())
	arr = list(map(int, input().split()))
	a0 = arr.count(0)
	a1 = arr.count(1)
	if a0 <= a1:
		print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	operation_list = list(a)
	bitwise_OR = []
	bitwise_AND = []
	if (len(a) - 1) % 2 == 0:
		for j in range((len(a) - 1) // 2):
			if 1 in operation_list and 0 in operation_list:
				bitwise_OR.append(1)
				bitwise_OR.append(0)
				operation_list.remove(1)
				operation_list.remove(0)
				operation_list.append(bitwise_OR[0] | bitwise_OR[1])
				bitwise_OR.remove(1)
				bitwise_OR.remove(0)
			elif 1 in operation_list and 0 not in operation_list:
				bitwise_OR.append(1)
				bitwise_OR.append(1)
				operation_list.remove(1)
				operation_list.remove(1)
				operation_list.append(bitwise_OR[0] | bitwise_OR[1])
				bitwise_OR.remove(1)
				bitwise_OR.remove(1)
			else:
				bitwise_OR.append(0)
				bitwise_OR.append(0)
				operation_list.remove(0)
				operation_list.remove(0)
				operation_list.append(bitwise_OR[0] | bitwise_OR[1])
				bitwise_OR.remove(0)
				bitwise_OR.remove(0)
			if 1 in operation_list and 0 in operation_list:
				bitwise_AND.append(1)
				bitwise_AND.append(0)
				operation_list.remove(1)
				operation_list.remove(0)
				operation_list.append(bitwise_AND[0] & bitwise_AND[1])
				bitwise_AND.remove(1)
				bitwise_AND.remove(0)
			elif 1 not in operation_list and 0 in operation_list:
				bitwise_AND.append(0)
				bitwise_AND.append(0)
				operation_list.remove(0)
				operation_list.remove(0)
				operation_list.append(bitwise_AND[0] & bitwise_AND[1])
				bitwise_AND.remove(0)
				bitwise_AND.remove(0)
			else:
				bitwise_AND.append(1)
				bitwise_AND.append(1)
				operation_list.remove(1)
				operation_list.remove(1)
				operation_list.append(bitwise_AND[0] & bitwise_AND[1])
				bitwise_AND.remove(1)
				bitwise_AND.remove(1)
		print(*operation_list)
	else:
		for j in range((len(a) - 1) // 2):
			if 1 in operation_list and 0 in operation_list:
				bitwise_OR.append(1)
				bitwise_OR.append(0)
				operation_list.remove(1)
				operation_list.remove(0)
				operation_list.append(bitwise_OR[0] | bitwise_OR[1])
				bitwise_OR.remove(1)
				bitwise_OR.remove(0)
			elif 1 in operation_list and 0 not in operation_list:
				bitwise_OR.append(1)
				bitwise_OR.append(1)
				operation_list.remove(1)
				operation_list.remove(1)
				operation_list.append(bitwise_OR[0] | bitwise_OR[1])
				bitwise_OR.remove(1)
				bitwise_OR.remove(1)
			else:
				bitwise_OR.append(0)
				bitwise_OR.append(0)
				operation_list.remove(0)
				operation_list.remove(0)
				operation_list.append(bitwise_OR[0] | bitwise_OR[1])
				bitwise_OR.remove(0)
				bitwise_OR.remove(0)
			if 1 in operation_list and 0 in operation_list:
				bitwise_AND.append(1)
				bitwise_AND.append(0)
				operation_list.remove(1)
				operation_list.remove(0)
				operation_list.append(bitwise_AND[0] & bitwise_AND[1])
				bitwise_AND.remove(1)
				bitwise_AND.remove(0)
			elif 1 not in operation_list and 0 in operation_list:
				bitwise_AND.append(0)
				bitwise_AND.append(0)
				operation_list.remove(0)
				operation_list.remove(0)
				operation_list.append(bitwise_AND[0] & bitwise_AND[1])
				bitwise_AND.remove(0)
				bitwise_AND.remove(0)
			else:
				bitwise_AND.append(1)
				bitwise_AND.append(1)
				operation_list.remove(1)
				operation_list.remove(1)
				operation_list.append(bitwise_AND[0] & bitwise_AND[1])
				bitwise_AND.remove(1)
				bitwise_AND.remove(1)
		if 1 in operation_list and 0 in operation_list:
			bitwise_OR.append(1)
			bitwise_OR.append(0)
			operation_list.remove(1)
			operation_list.remove(0)
			operation_list.append(bitwise_OR[0] | bitwise_OR[1])
			bitwise_OR.remove(1)
			bitwise_OR.remove(0)
		elif 1 in operation_list and 0 not in operation_list:
			bitwise_OR.append(1)
			bitwise_OR.append(1)
			operation_list.remove(1)
			operation_list.remove(1)
			operation_list.append(bitwise_OR[0] | bitwise_OR[1])
			bitwise_OR.remove(1)
			bitwise_OR.remove(1)
		else:
			bitwise_OR.append(0)
			bitwise_OR.append(0)
			operation_list.remove(0)
			operation_list.remove(0)
			operation_list.append(bitwise_OR[0] | bitwise_OR[1])
			bitwise_OR.remove(0)
			bitwise_OR.remove(0)
		print(*operation_list)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ones = sum(arr)
	zeroes = n - ones
	if ones < zeroes:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	ar = input()
	if ar.count('0') <= ar.count('1'):
		print(1)
	else:
		print(0)


t = input()
for c in range(0, int(t)):
	n = int(input())
	ar = input()
	if ar.count('0') <= ar.count('1'):
		print(1)
	else:
		print(0)


import sys
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split(' ')))
	dct = {}
	(dct[1], dct[0]) = (0, 0)
	for item in a:
		dct[item] = dct.get(item, 0) + 1
	while dct[0] and dct[1]:
		dct[0] -= 1
		dct[1] -= 1
	if dct[0] == 0:
		print('1')
	else:
		print('0')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	z = 0
	p = 1
	if a.count(p) >= a.count(z):
		print('1')
	else:
		print('0')


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	zero_count = arr.count(0)
	ones_count = arr.count(1)
	if zero_count > ones_count:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	ones = l.count(1)
	zeros = n - ones
	if ones >= zeros:
		print(1)
	else:
		print(0)


n = int(input())
while n:
	n = n - 1
	k = int(input())
	l = list(map(int, input().split()))
	a = l.count(1)
	b = l.count(0)
	if a == b or a > b:
		print('1')
	else:
		print('0')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(0)
	b = l.count(1)
	if a > b:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	a = input().split()
	numbers = sorted(a)
	result = ''
	while True:
		if len(numbers) == 1:
			break
		for i in range(len(numbers[-1])):
			if numbers[1][i] == '1' or numbers[0][i] == '1':
				result += '1'
			else:
				result += '0'
		numbers.pop(0)
		numbers.pop(0)
		numbers.insert(0, result)
		result = ''
		if len(numbers) == 1:
			break
		for i in range(len(numbers[-1])):
			if numbers[-1][i] == '1' and numbers[-2][i] == '1':
				result += '1'
			else:
				result += '0'
		numbers.pop(-1)
		numbers.pop(-1)
		numbers.append(result)
		result = ''
	print(numbers[0])


for _ in range(int(input())):
	n = int(input())
	a = input()
	c1 = a.count('0')
	if c1 > n // 2:
		print(0)
	else:
		print(1)


T = int(input())
for i in range(T):
	N = int(input())
	arr = [int(i) for i in input().split(' ', N - 1)]
	oneCount = 0
	zeroCount = 0
	for j in range(N):
		if arr[j] == 0:
			zeroCount = zeroCount + 1
		else:
			oneCount = oneCount + 1
	if oneCount >= zeroCount:
		print('1')
	else:
		print('0')


T = int(input())
for j in range(T):
	n = int(input())
	a1 = []
	a2 = []
	li = list(input().split())
	li = list(map(int, li))
	for i in range(0, n):
		if li[i] == 0:
			a1.append(0)
		else:
			a2.append(1)
	if len(a1) <= len(a2):
		print('1')
	else:
		print('0')


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(i) for i in input().split()]
	l = arr.count(0)
	r = arr.count(1)
	if l > r:
		print(0)
	else:
		print(1)
	t = t - 1


n = int(input())
for i in range(n):
	p = int(input())
	l = list(map(int, input().split()))
	a0 = l.count(0)
	a1 = l.count(1)
	if a0 > a1:
		print(0)
	else:
		print(1)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(cnt_1, cnt_0) = (0, 0)
	for i in arr:
		if i == 1:
			cnt_1 += 1
		else:
			cnt_0 += 1
	if cnt_1 >= cnt_0:
		print(1)
	else:
		print(0)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(cnt_1, cnt_0) = (0, 0)
	for i in arr:
		if i == 1:
			cnt_1 += 1
		else:
			cnt_0 += 1
	k = 0
	while cnt_0 != 0 and cnt_1 != 0:
		if k % 2 == 0:
			cnt_0 -= 1
		else:
			cnt_1 -= 1
		k += 1
	if cnt_1 != 0:
		print(1)
	else:
		print(0)


testCases = int(input())
for t in range(0, testCases):
	n = int(input())
	binaries = list(map(int, input().strip().split()))[:n]
	ones = binaries.count(1)
	zeros = n - ones
	if zeros > ones:
		print('0')
	else:
		print('1')


a = int(input())
for _ in range(a):
	b = int(input())
	c = input().split(' ')
	c = [int(x) for x in c]
	count_0 = c.count(0)
	count_1 = c.count(1)
	if count_0 > count_1:
		print(0)
	else:
		print(1)


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	one = sum(l)
	zero = n - one
	if one >= zero:
		print(1)
	else:
		print(0)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	L = input().split(' ')
	l = []
	for i in L:
		l.append(int(i))
	l.sort()
	if l.count(0) >= l.count(1) + 1:
		print(0)
	elif l.count(0) < l.count(1) + 1:
		print(1)


T = int(input())
for i in range(T):
	n = int(input())
	sen = list(map(str, input().split()))
	z = sen.count('0')
	o = sen.count('1')
	if z > o:
		print(0)
	else:
		print(1)


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def calc(s):
	ans = 0
	for ele in s:
		ans += ord(ele) - 96
	return ans

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(0) > l.count(1):
		print(0)
	else:
		print(1)
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	L = [int(j) for j in input().split()]
	(c1, c0) = (L.count(1), L.count(0))
	rem_numm = 0
	if c1 >= c0:
		rem_numm = 1
	elif c0 > c1:
		if abs(c0 - c1) == 1:
			if n % 2 == 0:
				rem_numm = 1
	print(rem_numm)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c1 = arr.count(1)
	c0 = n - c1
	if c0 > c1:
		print(0)
	elif c1 > c0:
		print(1)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(zr, on) = (0, 0)
	for i in lst:
		if i == 0:
			zr += 1
		else:
			on += 1
	print([0, 1][on >= zr])


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	while len(l) > 1:
		if 1 in l and 0 in l:
			l.remove(0)
		elif l.count(1) > 1:
			l.remove(1)
		elif l.count(0) > 1:
			l.remove(0)
		if 1 in l and 0 in l:
			l.remove(1)
		elif l.count(0) > 1:
			l.remove(0)
		elif l.count(1) > 1:
			l.remove(1)
	print(l[0])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(one, zero) = (0, 0)
	for i in range(n):
		if l[i] == 0:
			zero = zero + 1
		else:
			one = one + 1
	if one >= zero:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	n0 = l.count(0)
	n1 = l.count(1)
	if n0 > n1:
		print(0)
	else:
		print(1)


while True:
	try:
		for _ in range(int(input())):
			inn = int(input())
			arr = input().split()
			arr_1 = []
			arr_0 = []
			for i in range(inn):
				arr[i] = int(arr[i])
				if arr[i] == 1:
					arr_1.append(arr[i])
				else:
					arr_0.append(arr[i])
			if len(arr_1) >= len(arr_0):
				print(1)
			else:
				print(0)
	except:
		break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ones = arr.count(1)
	zeroes = arr.count(0)
	if ones > zeroes:
		print('1')
	elif ones == zeroes:
		print('1')
	else:
		print('0')


import numpy as np
for i in range(int(input())):
	n = int(input())
	arr = np.array([int(i) for i in input().split()])
	one = sum(arr)
	zero = n - one
	if one == zero or one > zero:
		print(1)
	else:
		print(0)


def finalOut(l, lst):
	n1 = sum(lst)
	n0 = l - n1
	if n1 >= n0:
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	l = int(input())
	lst = list(map(int, input().split()))
	print(finalOut(l, lst))


def finalOut(l, lst):
	n0 = 0
	n1 = 0
	for i in lst:
		if i == 0:
			n0 += 1
		else:
			n1 += 1
	a = True
	while n0 and n1:
		if a:
			n0 -= 1
			a = False
		else:
			n1 -= 1
			a = True
	if n0 == 0:
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	l = int(input())
	lst = list(map(int, input().split()))
	print(finalOut(l, lst))


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ones = sum(arr)
	zeros = n - ones
	if ones == zeros or ones > zeros:
		print(1)
	else:
		print(0)


for i in range(int(input())):
	N = int(input())
	arr = [int(i) for i in input().split()]
	t = 1
	one = arr.count(1)
	zero = arr.count(0)
	for i in range(N):
		if len(arr) != 1:
			if t == -1:
				if one != 0:
					arr.remove(1)
					one -= 1
				else:
					arr.remove(0)
			elif zero != 0:
				arr.remove(0)
				zero -= 1
			else:
				arr.remove(1)
			t = -t
	print(*arr)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a0 = a.count(0)
	a1 = a.count(1)
	if a1 >= a0:
		print(1)
	else:
		print(0)


def solve(arr):
	ones = 0
	zeros = 0
	for num in arr:
		if num == 1:
			ones += 1
		else:
			zeros += 1
	alice = True
	while ones + zeros > 1:
		if alice:
			if ones >= 1 and zeros >= 1 or ones == 0:
				zeros -= 1
			else:
				ones -= 1
		elif ones >= 1 and zeros >= 1 or zeros == 0:
			ones -= 1
		else:
			zeros -= 1
		alice = not alice
	return 0 if zeros == 1 else 1
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(arr))


t = int(input())
for i in range(t):
	N = int(input())
	arr = [int(j) for j in input().split()]
	x = arr.count(0)
	y = arr.count(1)
	if y >= x:
		print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	n1 = int(input())
	l1 = list(map(int, input().split()))
	c1 = l1.count(1)
	c0 = l1.count(0)
	if c1 > c0 or c1 == c0:
		print(1)
	else:
		print(0)