You are given two arrays $a$ and $b$ of $n$ elements, each element is either $0$ or $1$.

You can make operations of $2$ kinds.

Pick an index $i$ and change $a_i$ to $1-a_i$.

Rearrange the array $a$ however you want.

Find the minimum number of operations required to make $a$ equal to $b$.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 400$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$) — the length of the arrays $a$ and $b$.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($a_i$ is $0$ or $1$), representing the array $a$.

The third line of each test case contains $n$ space-separated integers $b_1,b_2,\ldots,b_n$ ($b_i$ is $0$ or $1$), representing the array $b$.


-----Output-----

For each test case, print the minimum number of operations required to make $a$ equal to $b$.


-----Examples-----

Input
5
3
1 0 1
0 0 1
4
1 1 0 0
0 1 1 1
2
1 1
1 1
4
1 0 0 1
0 1 1 0
1
0
1
Output
1
2
0
1
1


-----Note-----

In the first case, we need only one operation: change $a_1$ to $1-a_i$. Now $a = [0, 0]$ which is equal to $b$.

In the second case, the optimal way is to rearrange $a$ to get the array $[0, 1, 11$. Now $a = [0, 0, 1]$ which is equal to $b$.

In the second case, one of optimal ways would be to first change $a_3$ to $1 - a_3$, then rearrange $a$.

In the third case, no operation is needed.

In the fourth case, the optimal way is to rearrange $a$ to get the array $[0, 1, 1, 0]$.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
def func(n, a, b):
	error_zero = 0
	error_one = 0
	for i in range(n):
		if a[i] == 0 and b[i] == 1:
			error_zero += 1
		elif a[i] == 1 and b[i] == 0:
			error_one += 1
	rearrange = min(error_zero, error_one)
	if rearrange > 0:
		error_one -= rearrange
		error_zero -= rearrange
		step = 1
	else:
		step = 0
	return max(error_one, error_zero) + step
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in list(input().split(' '))]
	b = [int(x) for x in list(input().split(' '))]
	print(func(n, a, b))


def cringe(a, b, n):
	cnt = 0
	cnt1a = 0
	cnt1b = 0
	for i in range(n):
		if a[i] != b[i]:
			cnt += 1
		if a[i] == 1:
			cnt1a += 1
		if b[i] == 1:
			cnt1b += 1
	print(min(abs(cnt1b - cnt1a) + 1, cnt))
k = int(input())
for i in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	cringe(a, b, n)


t = int(input())
p = 0
for _ in range(t):
	n = int(input())
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	sum1 = 0
	sum2 = 0
	if n == 1:
		if a1[0] - a2[0] == 0:
			print('0')
		else:
			print('1')
		pass
	else:
		for i in range(n):
			if a1[i] - a2[i] == -1:
				count1 = 1
			if a1[i] == 1:
				sum1 += 1
			if a2[i] == 1:
				sum2 += 1
			if a1[i] - a2[i] == 1:
				count2 = 1
		print(max(sum1, sum2) - min(sum1, sum2) + (count1 + count2) // 2)


t = int(input())
for test in range(t):
	n = int(input())
	a = input().split()
	b = input().split()
	res = 0
	for i in range(n):
		if a[i] == '1':
			res += 1
		if b[i] == '1':
			res -= 1
	q = 0
	if res >= 0:
		for i in range(n):
			if b[i] == '1':
				if a[i] == '0':
					q = 1
		print(res + q)
	if res < 0:
		for i in range(n):
			if a[i] == '1':
				if b[i] == '0':
					q = 1
		print(abs(res) + q)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ac = sum(a)
	bc = sum(b)
	if ac <= bc:
		flag = 0
		for i in range(n):
			if a[i] == 1 and b[i] == 0:
				flag = 1
				break
		print(abs(ac - bc) + flag)
	else:
		flag = 0
		for i in range(n):
			if a[i] == 0 and b[i] == 1:
				flag = 1
				break
		print(abs(ac - bc) + flag)


t = int(input())
for q in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	k = n
	a1 = 0
	b1 = 0
	for i in range(n):
		if a[i] == b[i]:
			k -= 1
		if a[i] == 1:
			a1 += 1
		if b[i] == 1:
			b1 += 1
	if k == 0:
		print(0)
	elif k == abs(a1 - b1):
		print(k)
	else:
		print(abs(a1 - b1) + 1)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	dif1 = abs(sum(A) - sum(B))
	dif2 = sum([A[i] != B[i] for i in range(N)])
	print(dif1 + 1 * (dif2 > dif1))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	na = a.count(1)
	nb = b.count(1)
	diff = sum((abs(x - y) for (x, y) in zip(a, b)))
	s = abs(na - nb)
	print(diff if s == diff else s + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sum_a = sum(a)
	sum_b = sum(b)
	diff = 0
	for j in range(n):
		if a[j] != b[j]:
			diff += 1
	if abs(sum_a - sum_b) == diff:
		print(diff)
		continue
	print(abs(sum_a - sum_b) + 1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	if arr == brr:
		print(0)
		continue
	a1 = arr.count(1)
	a0 = n - a1
	b1 = brr.count(1)
	b0 = n - b1
	if a1 == b1:
		print(1)
		continue
	if a1 > b1:
		d = a1 - b1
		f = False
		for i in range(n):
			if arr[i] == 0 and brr[i] == 1:
				f = True
				break
		if f:
			print(d + 1)
		else:
			print(d)
	else:
		d = a0 - b0
		f = False
		for i in range(n):
			if arr[i] == 1 and brr[i] == 0:
				f = True
				break
		if f:
			print(d + 1)
		else:
			print(d)


n = int(input())
for _ in range(n):
	l = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c1 = a.count(1)
	c2 = b.count(1)
	c = 0
	if a == b:
		print(0)
	elif c1 == c2:
		print(1)
	else:
		for i in range(len(a)):
			if a[i] != b[i]:
				c += 1
		print(min(abs(c1 - c2) + 1, c))


for _ in range(int(input())):
	length = int(input())
	lstA = list(map(int, input().split()))
	lstB = list(map(int, input().split()))
	counter = 0
	for i in range(length):
		if lstA[i] != lstB[i]:
			counter += 1
	a = lstA.count(0)
	b = lstB.count(0)
	r = abs(a - b)
	print(r if r == counter else r + 1)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	difbits = 0
	z1 = a.count(0)
	z2 = b.count(0)
	if z1 == z2:
		if a == b:
			print(0)
		else:
			print(1)
		continue
	for i in range(n):
		if a[i] != b[i]:
			difbits = difbits + 1
	other = abs(z1 - z2) + 1
	print(min(other, difbits))


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, ans) = (0, 0, 0)
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		if a[i] != b[i]:
			ans += 1
	ans = min(ans, abs(sum(a) - sum(b)) + 1)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(x, y, ok) = (0, 0, 0)
	x = sum(a)
	y = sum(b)
	for j in range(n):
		ok += a[j] != b[j]
	print(min(ok, abs(x - y) + 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a1 = a.count(1)
	b1 = b.count(1)
	s = 0
	for i in range(n):
		if a[i] == b[i]:
			s += 1
	if a1 == b1:
		if s == n:
			print(0)
		else:
			print(1)
	elif a1 > b1:
		if n - s == a1 - b1:
			print(a1 - b1)
		else:
			print(a1 - b1 + 1)
	elif n - s == b1 - a1:
		print(b1 - a1)
	else:
		print(b1 - a1 + 1)


for i in range(int(input())):
	m = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if a == b:
		print('0')
	else:
		res = 0
		zero_a = m - sum(a)
		zero_b = m - sum(b)
		one_a = sum(a)
		one_b = sum(b)
		if a != b and one_a == one_b and (zero_a == zero_b):
			print('1')
			continue
		if one_a > one_b:
			var = 1
		else:
			var = 0
		index = 0
		for (i, j) in zip(a, b):
			if i != j:
				if i == 1 and i == var:
					a[index] = 0
					zero_a += 1
					one_a -= 1
					res += 1
				elif i == 0 and i == var:
					a[index] = 1
					zero_a -= 1
					one_a += 1
					res += 1
			if one_a == one_b and zero_a == zero_b:
				break
			index += 1
		if a != b:
			res += 1
		print(res)


import sys
import math

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	cnt1 = sum(a)
	cnt2 = sum(b)
	ok = sum([a[i] != b[i] for i in range(n)])
	print(min(ok, abs(cnt1 - cnt2) + 1))
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c1 = 0
	c2 = 1
	cz1 = 0
	cz2 = 0
	for i in range(n):
		if a[i] != b[i]:
			c1 += 1
		if a[i] == 0:
			cz1 += 1
		if b[i] == 0:
			cz2 += 1
	print(min(c1, abs(cz1 - cz2) + 1))


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	b = input().split()
	a_count = 0
	b_count = 0
	for j in range(n):
		if a[j] == '1':
			a_count += 1
		if b[j] == '1':
			b_count += 1
	if a_count == b_count:
		if a == b:
			print(0)
		else:
			print(1)
	elif a_count > b_count:
		noOfChanges = a_count - b_count
		for j in range(n):
			if a[j] != b[j] and a[j] == '1':
				noOfChanges -= 1
				a[j] = '0'
			if noOfChanges <= 0:
				break
		if a == b:
			print(a_count - b_count)
		else:
			print(a_count - b_count + 1)
	else:
		noOfChanges = b_count - a_count
		for j in range(n):
			if a[j] != b[j] and b[j] == '1':
				noOfChanges -= 1
				b[j] = '0'
			if noOfChanges <= 0:
				break
		if a == b:
			print(b_count - a_count)
		else:
			print(b_count - a_count + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split(' ')
	b = input().split(' ')
	la = 0
	lb = 0
	for i in range(n):
		if a[i] == '1':
			la += 1
		if b[i] == '1':
			lb += 1
	if la == lb and a == b:
		print(0)
	elif la == lb and a != b:
		print(1)
	if la > lb:
		j = 0
		k = la - lb
		while k > 0:
			if b[j] == '0' and a[j] == '1':
				b[j] = '1'
				k -= 1
			j += 1
		if b == a:
			print(la - lb)
		else:
			print(la - lb + 1)
	if la < lb:
		j = 0
		k = lb - la
		while k > 0:
			if b[j] == '1' and a[j] == '0':
				a[j] = '1'
				k -= 1
			j += 1
		if b == a:
			print(lb - la)
		else:
			print(lb - la + 1)


n = int(input())
for i in range(n):
	size = int(input())
	arr1 = input()
	arr1 = arr1.split()
	onesin1 = arr1.count('1')
	arr2 = input()
	arr2 = arr2.split()
	onesin2 = arr2.count('1')
	if onesin1 == onesin2:
		for j in range(size):
			if arr1[j] != arr2[j]:
				print(1)
				break
		else:
			print(0)
	else:
		change = 0
		dif = onesin1 - onesin2
		if dif < 0:
			dif *= -1
		for j in range(size):
			if arr1[j] != arr2[j]:
				arr1[j] = arr2[j]
				dif -= 1
				change += 1
			if dif == 0:
				break
		for j in range(size):
			if arr1[j] != arr2[j]:
				print(change + 1)
				break
		else:
			print(change)


x = []
y = []
n = int(input())
for i in range(n):
	m = int(input())
	x.append(input().split(' '))
	y.append(input().split(' '))
for i in range(n):
	if x[i] == y[i]:
		print(0)
	elif x[i] in y[i]:
		print(1)
	else:
		l = 0
		for (j, k) in zip(x[i], y[i]):
			l += int(j != k)
		f = abs(x[i].count('1') - y[i].count('1')) + 1
		print(min(l, f))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = a[::-1]
	count = 0
	count1 = 0
	if a == b:
		print(0)
	elif sum(a) == sum(b):
		print(1)
	else:
		d = abs(sum(a) - sum(b))
		for i in range(n):
			if a[i] != b[i]:
				count += 1
		if d == count:
			print(d)
		else:
			print(d + 1)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if l1[i] != l2[i]:
			c += 1
	print(min(c, abs(sum(l1) - sum(l2)) + 1))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = a.count(1)
	y = b.count(1)
	ans = abs(x - y)
	res = 0
	for i in range(n):
		if a[i] != b[i]:
			res += 1
	if res == ans:
		print(ans)
	else:
		print(ans + 1)
	t -= 1


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	diff = abs(sum(a) - sum(b))
	result = diff
	i = 0
	while diff > 0:
		if a[i] != b[i]:
			a[i] = 1 - a[i]
			diff -= 1
		i += 1
	if a != b:
		result += 1
	print(result)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(cta, ctb) = (0, 0)
	eq = 0
	for i in range(N):
		if A[i] == 0:
			cta += 1
		if B[i] == 0:
			ctb += 1
		if A[i] == B[i]:
			eq += 1
	if cta == ctb and eq == N:
		print(0)
	elif cta == ctb:
		print(1)
	else:
		temp = min(abs(cta - ctb), abs(N - cta - (N - ctb)))
		ans = min(N - eq, temp + 1)
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	count = 0
	ans = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			count += 1
	if count == 0:
		print(0)
	else:
		one1 = a.count(1)
		zero1 = a.count(0)
		one2 = b.count(1)
		zero2 = b.count(0)
		if one1 == one2 and zero1 == zero2:
			ans += 1
		else:
			for i in range(len(a)):
				if a[i] == 1 and b[i] == 1:
					one1 -= 1
					one2 -= 1
			if one1 == 0 or one2 == 0:
				ans += abs(one2 - one1)
			else:
				ans += abs(one2 - one1) + 1
		print(ans)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	dif = sum(a) - sum(b)
	if dif < 0:
		cnt = 0
		for i in range(n):
			if b[i] == 1 and a[i] == 0 and (cnt < abs(dif)):
				ans += 1
				cnt += 1
				a[i] = 1
		if b != a:
			ans += 1
	else:
		cnt = 0
		for i in range(n):
			if b[i] == 0 and a[i] == 1 and (cnt < abs(dif)):
				ans += 1
				cnt += 1
				a[i] = 0
		if b != a:
			ans += 1
	print(ans)
	t = t - 1


t = int(input())
i = 1
while True:
	if i > t:
		break
	n = int(input())
	a = [int(x) for x in input().split(' ', n - 1)]
	b = [int(y) for y in input().split(' ', n - 1)]
	p = q = 0
	for x in a:
		if x == 0:
			p += 1
	for y in b:
		if y == 0:
			q += 1
	k = abs(p - q)
	w = j = 0
	while True:
		if w == n:
			break
		if a[w] != b[w]:
			j = j + 1
		w += 1
	if j > k:
		k += 1
	print(k)
	i = i + 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a1 = b1 = 0
	count = 0
	for i in range(n):
		if a[i] == 1:
			a1 += 1
	for i in range(n):
		if b[i] == 1:
			b1 += 1
		if b[i] != a[i]:
			count += 1
	ans = abs(b1 - a1)
	if count > ans:
		ans += 1
	print(ans)


def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		cnt = 0
		for i in range(n):
			if a[i] != b[i]:
				cnt += 1
		if cnt != abs(sum(a) - sum(b)):
			print(abs(sum(a) - sum(b)) + 1)
		else:
			print(cnt)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a1 = 0
	for i in range(n):
		a1 += a[i] != b[i]
	a2 = 1
	a.sort()
	b.sort()
	for i in range(n):
		a2 += a[i] != b[i]
	print(min(a1, a2))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sum(a)
	d = sum(b)
	cnt = 0
	for i in range(n):
		if a[i] != b[i]:
			cnt += 1
	if c == d and cnt == 0:
		print(0)
		continue
	elif c == d:
		print(1)
		continue
	elif abs(c - d) == cnt:
		print(abs(c - d))
	else:
		print(abs(c - d) + 1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	if a == b:
		print(0)
		continue
	x = [1 for i in range(len(a)) if a[i] != b[i]]
	ans = 0
	print(min(len(x), abs(a.count(1) - b.count(1)) + 1))


n = int(input())
for i in range(n):
	index = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = abs(sum(a) - sum(b))
	cnt = ans
	for x in range(index):
		if cnt <= 0:
			break
		if a[x] != b[x]:
			a[x] = 1 - a[x]
			cnt -= 1
	if a == b:
		print(ans)
	else:
		print(ans + 1)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(c1, c2) = (0, 0)
	for i in range(n):
		if a[i] == 0 and b[i] == 1:
			c1 += 1
		if a[i] == 1 and b[i] == 0:
			c2 += 1
	if c1 == 0 and c2 == 0:
		print(0)
	elif c1 == 0 or c2 == 0:
		print(max(c1, c2))
	else:
		print(abs(c1 - c2) + 1)


for _ in range(int(input())):
	num = int(input())
	x = input().split()
	y = input().split()
	sol = 0
	for i in range(num):
		if x[i] != y[i]:
			sol += 1
	print(min(sol, abs(x.count('1') - y.count('1')) + 1))


for _ in range(int(input())):
	N = int(input())
	p = input().split()
	q = input().split()
	res = 0
	for i in range(N):
		if p[i] != q[i]:
			res += 1
	print(min(res, abs(p.count('1') - q.count('1')) + 1))


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	na = nb = 0
	ueq = 0
	for j in range(n):
		if a[j] == 1:
			na += 1
		if b[j] == 1:
			nb += 1
		if a[j] != b[j]:
			ueq += 1
	dif = abs(na - nb)
	if ueq == 0:
		print(0)
	elif ueq > 0 and dif == 0:
		print(1)
	elif ueq == dif:
		print(dif)
	else:
		print(1 + dif)


t = int(input())
output = []
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	if a == b:
		output.append(0)
		continue
	else:
		k = 0
		for i in range(n):
			if a[i] != b[i]:
				k += 1
		output.append(min(k, abs(a.count(0) - b.count(0)) + 1))
for o in output:
	print(o)


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = list(map(int, input().split(sep=' ')))
	arr2 = list(map(int, input().split(sep=' ')))
	k = abs(arr1.count(1) - arr2.count(1))
	cnt = 0
	for j in range(n):
		if arr1[j] != arr2[j]:
			cnt = cnt + 1
	if arr1 == arr2:
		print(0)
	elif arr1.count(1) == arr2.count(1):
		print(1)
	else:
		print(min(k + 1, cnt))


from sys import stdout
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(a_zero, b_zero, a_one, b_one) = (0, 0, 0, 0)
	flag = True
	d_ch = 0
	for i in range(n):
		if a[i] != b[i]:
			flag = False
			d_ch += 1
		if a[i] == 0:
			a_zero += 1
		else:
			a_one += 1
		if b[i] == 0:
			b_zero += 1
		else:
			b_one += 1
	if a_zero == b_zero and a_one == b_one:
		if flag:
			print(0)
		else:
			print(1)
	else:
		ans = min(abs(a_zero - b_zero), abs(a_one - b_one))
		if ans + 1 <= d_ch:
			print(ans + 1)
		else:
			print(d_ch)
	stdout.flush()


for x in range(int(input())):
	l = int(input())
	a = input().split()
	b = input().split()
	a0 = a.count('0')
	a1 = l - a0
	b0 = b.count('0')
	b1 = l - b0
	c = l - min([a0, b0]) - min([a1, b1])
	d = 0
	for i in range(l):
		if a[i] != b[i]:
			d += 1
	e = 0
	if d != c:
		e += 1
	print(c + e)


for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += abs(a[i] - b[i])
	ans = min(ans, 1 + abs(sum(a) - sum(b)))
	print(ans)


cases = int(input())

def solution(arr1, arr2):
	vals1 = {}
	vals2 = {}
	(vals1[0], vals2[0]) = (0, 0)
	(vals1[1], vals2[1]) = (0, 0)
	ret = 0
	nin = 0
	for i in range(len(arr1)):
		vals1[arr1[i]] = vals1.get(arr1[i], 0) + 1
		vals2[arr2[i]] = vals2.get(arr2[i], 0) + 1
		if arr1[i] != arr2[i]:
			nin += 1
	if nin == 0:
		return 0
	change = 0
	if vals1 == vals2:
		return 1
	else:
		change += 1
	diff0 = abs(vals1[0] - vals2[0])
	diff1 = abs(vals1[1] - vals2[1])
	change += min(diff0, diff1)
	return min(change, nin)
for i in range(cases):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	print(solution(arr1, arr2))


a = int(input())
sp = []
for i in range(a):
	o = []
	li = 0
	j = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	n0 = 0
	n1 = 0
	w0 = 0
	w1 = 0
	for y in b:
		if y == 1:
			n1 += 1
		else:
			n0 += 1
	for p in a:
		if p == 1:
			w1 += 1
		else:
			w0 += 1
	if n1 > w1:
		li += n1 - w1
	elif n0 > w0:
		li += n0 - w0
	k = 0
	for d in range(j):
		if k == li and a[d] != b[d]:
			li += 1
			break
		elif a[d] != b[d]:
			k += 1
	sp.append(li)
for t in sp:
	print(t)


n = int(input())
result = []
for i in range(n):
	l = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ans = 0
	sum = a.count(1) - b.count(1)
	for j in range(l):
		ans += a[j] ^ b[j]
	result.append(min(ans, 1 + abs(sum)))
print(*result, sep='\n')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if a == b:
		print(0)
	elif n == 1:
		print(1)
	elif len(set(a)) == 1 or len(set(b)) == 1:
		print(abs(a.count(1) - b.count(1)))
	else:
		k = 0
		s = 0
		for j in range(n):
			if a[j] == b[j] == 1:
				s += 1
		ac = a.count(1)
		bc = b.count(1)
		if s != bc and bc <= ac or (s != ac and ac <= bc):
			k += 1
		print(k + abs(a.count(1) - b.count(1)))


from operator import sub
n = int(input())
ris = [[]] * n
for i in range(n):
	lung = input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	diversi = list(map(sub, a, b))
	o1 = diversi.count(1)
	o2 = diversi.count(-1)
	if o1 == 0 or o2 == 0:
		ris[i] = o1 + o2
	else:
		ris[i] = abs(o1 - o2) + 1
print(*ris, sep='\n')


def solve():
	n = int(input())
	lstA = list(map(int, input().split()))
	lstB = list(map(int, input().split()))
	flag = True
	oneA = 0
	oneB = 0
	c = 0
	for i in range(n):
		if lstA[i]:
			oneA += 1
		if lstB[i]:
			oneB += 1
		if lstA[i] != lstB[i]:
			c += 1
			flag = False
	if flag:
		print(0)
		return
	else:
		print(min(c, 1 + abs(oneA - oneB)))
t = int(input())
while t:
	solve()
	t -= 1


import sys
input = sys.stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		if a == b:
			print(0)
		else:
			(s, t, u) = (0, 0, 0)
			for i in range(n):
				s += a[i]
				t += b[i]
				if a[i] != b[i]:
					u += 1
			if s == t:
				print(1)
			else:
				print(min(abs(t - s) + 1, u))
main()


for _ in range(int(input())):
	n = int(input())
	s = 0
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	for i in range(n):
		s += int(a[i] != b[i])
	print(min(s, abs(sum(a) - sum(b)) + 1))


t = int(input())
n = list([0] * 400)
a = list([[0] * 100] * 400)
b = list([[0] * 100] * 400)
for i in range(0, t):
	n[i] = int(input())
	a[i] = list(map(int, input().split()))
	b[i] = list(map(int, input().split()))
for i in range(0, t):
	x = sum(a[i])
	x2 = sum(b[i])
	y = n[i] - x
	y2 = n[i] - x2
	d = abs(x - x2)
	if abs(y - y2) < d:
		d = abs(y - y2)
	s = 0
	for l in range(0, n[i]):
		if a[i][l] != b[i][l]:
			s = s + 1
		if s > d:
			d = d + 1
			break
	print(d)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = a.count(1)
	y = b.count(1)
	c = 0
	for i in range(n):
		if a[i] != b[i]:
			c += 1
	if a == b:
		print(0)
	elif x == y:
		print(1)
	elif c == abs(x - y):
		print(c)
	else:
		print(1 + abs(x - y))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	summ = sum(a) - sum(b)
	ans = 0
	for i in range(n):
		ans += a[i] ^ b[i]
	ans = min(ans, 1 + abs(summ))
	print(ans)
	t -= 1


def dif(n, a, b):
	difference = 0
	for i in range(n):
		if a[i] + b[i] == 1:
			difference += 1
	return difference
t = int(input())
result = []
for j in range(t):
	num = int(input())
	a = []
	b = []
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	min_change = dif(num, a, b)
	max_change = abs(a.count(0) - b.count(0)) + 1
	result.append(min(min_change, max_change))
for el in result:
	print(el)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	a = a.split()
	b = input()
	b = b.split()
	s = 0
	for x in range(n):
		if a[x] != b[x]:
			s += 1
	k = abs(a.count('1') - b.count('1'))
	if s == k:
		print(k)
	else:
		print(k + 1)


for i in range(int(input())):
	s = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(a1, b1) = (0, 0)
	a1 = a.count(1)
	b1 = b.count(1)
	c = 0
	for j in range(len(a)):
		if a[j] != b[j]:
			c += 1
	print(min(c, abs(a1 - b1) + 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	oa = a.count(1)
	ob = b.count(1)
	p = abs(oa - ob) + 1
	c = 0
	for i in range(n):
		if a[i] != b[i]:
			c += 1
	print(min(p, c))


t = int(input())
for x in range(t):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	b = [int(i) for i in input().split(' ')]
	count = [a.count(0), b.count(0)]
	dif = 0
	for i in range(n):
		dif += a[i] != b[i]
	if count[0] != count[1]:
		print(min(abs(count[0] - count[1]) + 1, dif))
	else:
		print(int(dif != 0))


t = int(input())
for i in range(t):
	s = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	to = 1
	for i in range(s):
		if a[i] != b[i]:
			c += 1
	a.sort()
	b.sort()
	for i in range(s):
		if a[i] != b[i]:
			to += 1
	print(min(c, to))


t = int(input())
for i in range(t):
	k = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = sum(a)
	l = sum(b)
	p = 0
	c = 0
	for i in range(k):
		if a[i] != b[i]:
			c = c + 1
	if s > l:
		p = s - l
	else:
		p = l - s
	print(min(p + 1, c))


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		st1 = list(map(int, input().split()))
		st2 = list(map(int, input().split()))
		s1 = 0
		s2 = 0
		num_dif = 0
		for i in range(n):
			s1 += st1[i]
			s2 += st2[i]
			if st1[i] != st2[i]:
				num_dif += 1
		val = max(s1 - s2, s2 - s1)
		if num_dif <= val:
			print(val)
		else:
			print(val + 1)
main()


t = int(input())
A = []
B = []
for i in range(t):
	n = int(input())
	a = [int(p) for p in input().split()]
	b = [int(p) for p in input().split()]
	A.append(a)
	B.append(b)
for i in range(t):
	arr1 = A[i]
	arr2 = B[i]
	lah = 0
	for j in range(len(arr1)):
		if arr1[j] != arr2[j]:
			lah += 1
	satu = arr1.count(1)
	dua = arr2.count(1)
	bruh = abs(satu - dua) + 1
	if lah == abs(satu - dua):
		bruh -= 1
	if lah == 0:
		print(0)
	else:
		print(bruh)


from sys import setrecursionlimit, stdin
setrecursionlimit(1 << 20)
readline = stdin.readline
MOD = 998244353

def I():
	return int(readline())

def ST():
	return readline()[:-1]

def LI():
	return list(map(int, readline().split()))

def LII():
	return list(map(lambda x: int(x) - 1, readline().split()))

def LF(x, func):
	return [func() for _ in [0] * x]

def SPI():
	return map(int, readline().split())

def SPII():
	return map(lambda x: int(x) - 1, readline().split())

def FIE(x):
	return [readline()[:-1] for _ in [0] * x]

def solve():
	N = I()
	A = LI()
	B = LI()
	ans1 = sum((a != b for (a, b) in zip(A, B)))
	A.sort()
	B.sort()
	ans2 = 1 + sum((a != b for (a, b) in zip(A, B)))
	print(min(ans1, ans2))
t = I()
for _ in range(t):
	solve()


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi, isqrt
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	a = L()
	b = L()
	(e1, e2) = (0, 0)
	for i in a:
		if i % 2 == 0:
			e1 += 1
	for i in b:
		if i % 2 == 0:
			e2 += 1
	x = 0
	for i in range(n):
		if a[i] != b[i]:
			x += 1
	print(min(x, abs(e1 - e2) + 1))


def main():
	i = int(input())
	for _ in range(i):
		n = int(input().strip('\r\n'))
		a = [int(x) for x in input().strip('\r\n').split()]
		b = [int(x) for x in input().strip('\r\n').split()]
		ab = False
		ba = False
		res = 0
		for (ai, bi) in zip(a, b):
			if ai > bi:
				ab = True
			if bi > ai:
				ba = True
		res = sum(a) - sum(b)
		if res < 0:
			res = -res
		if ab and ba:
			res += 1
		print(res)
main()


def foo(n, a, b):
	ans1 = 0
	for i in range(n):
		if a[i] != b[i]:
			ans1 += 1
	a.sort()
	b.sort()
	ans2 = 1
	for i in range(n):
		if a[i] != b[i]:
			ans2 += 1
	return min(ans1, ans2)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	print(foo(n, a, b))


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if arr1[i] != arr2[i]:
			ans += 1
	ans = min(ans, abs(sum(arr1) - sum(arr2)) + 1)
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	ans = cnt1 = cnt2 = 0
	for i in range(n):
		if A[i] != B[i]:
			ans += 1
		cnt1 += A[i]
		cnt2 += B[i]
	return min(abs(cnt2 - cnt1) + 1, ans)
for _ in range(int(input())):
	print(solve())


t = int(input())
for tt in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	op1 = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			op1 += 1
	a.sort()
	b.sort()
	op2 = 1
	for i in range(len(a)):
		if a[i] != b[i]:
			op2 += 1
	print(min(op1, op2))


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a, b):
	if a == b:
		print(0)
		return
	za = a.count(0)
	zb = b.count(0)
	diff = 0
	for i in range(n):
		if a[i] != b[i]:
			diff += 1
	ops = min(1 + abs(a.count(0) - b.count(0)), diff)
	print(ops)
t = ni()
for case in range(t):
	n = ni()
	b = nl()
	a = nl()
	solve(n, a, b)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			ans += 1
	ans = min(ans, abs(sum(a) - sum(b)) + 1)
	return ans
t = int(input())
while t:
	print(solve())
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	r1 = b.count(1)
	a1 = a.count(1)
	ans = 0
	for i in range(n):
		if a[i] != b[i]:
			ans += 1
	print(min(ans, abs(r1 - a1) + 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	aone = a.count(1)
	bone = b.count(1)
	azero = a.count(0)
	bzero = b.count(0)
	if aone == bone:
		if a == b:
			print(0)
		else:
			print(1)
	else:
		ans1 = 0
		for i in range(n):
			if a[i] != b[i]:
				ans1 += 1
		ans2 = 0
		ans2 = min(abs(azero - bzero), abs(aone - bone)) + 1
		print(min(ans1, ans2))


import sys
input = sys.stdin.readline
from math import ceil, comb
list_input = lambda x=int: list(map(x, input().strip().split()))
mult_input = lambda x=int: map(x, input().strip().split())

def solve():
	n = int(input())
	a = list_input()
	b = list_input()
	diff = 0
	zeroa = a.count(0)
	zerob = b.count(0)
	ans = abs(zerob - zeroa)
	for i in range(n):
		if a[i] != b[i]:
			diff += 1
	if ans == 0:
		if diff:
			return 1
		return 0
	if diff == ans:
		return ans
	return ans + 1
for _ in range(int(input())):
	print(solve())


t = int(input())
for _ in range(t):
	q = int(input())
	w = list(map(int, input().split()))
	e = list(map(int, input().split()))
	r = w.count(1)
	y = e.count(1)
	z = abs(r - y)
	h = z
	j = False
	for i in range(q):
		if w[i] != e[i] and z > 0:
			w[i] = e[i]
			z -= 1
		elif w[i] != e[i]:
			j = True
	if j:
		h += 1
	print(h)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	an = a.count(1)
	bn = b.count(1)
	if an == bn:
		f = 0
		for i in range(n):
			if a[i] != b[i]:
				f = 1
				break
		print(1) if f else print(0)
	else:
		diff = abs(an - bn)
		count = diff
		f = 0
		for i in range(n):
			if a[i] != b[i] and diff == 0:
				f = 1
				break
			elif a[i] != b[i]:
				diff -= 1
		print(count + 1) if f else print(count)


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	sa = sum(a)
	sb = sum(b)
	ans = abs(sa - sb)
	for i in range(n):
		if sa < sb and a[i] == 0 and (b[i] == 1):
			sa += 1
			a[i] = 1
		if sa > sb and a[i] == 1 and (b[i] == 0):
			sa -= 1
			a[i] = 0
	if a != b:
		ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(a_count, b_count) = (0, 0)
	for ai in a:
		if ai == 1:
			a_count += 1
	for bi in b:
		if bi == 1:
			b_count += 1
	res1 = abs(a_count - b_count) + 1
	res2 = 0
	for i in range(n):
		if a[i] != b[i]:
			res2 += 1
	print(min(res1, res2))


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	count = 0
	for j in range(n):
		if a[j] != b[j]:
			count += 1
	ans = abs(a.count(1) - b.count(1))
	if count == 0:
		print(0)
	elif ans == 0:
		print(1)
	elif count == ans:
		print(count)
	else:
		print(ans + 1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	y = 0
	x = 0
	for i in range(n):
		if a[i] != b[i]:
			c += 1
		if a[i] == 1:
			x += 1
		if b[i] == 1:
			y += 1
	if abs(x - y) == c:
		print(abs(x - y))
	else:
		print(abs(x - y) + 1)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	z = abs(sum(x) - sum(y)) + 1
	count = 0
	for j in range(len(x)):
		if x[j] != y[j]:
			count += 1
	print(min(count, z))


def Solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a_sum = sum(a)
	b_sum = sum(b)
	n_changes = abs(a_sum - b_sum)
	ans = n_changes
	for i in range(n):
		if a[i] != b[i] and n_changes:
			n_changes -= 1
			a[i] = b[i]
	if a != b:
		ans += 1
	print(ans)

def main():
	t = int(input())
	for test in range(t):
		Solve()
main()


for jj in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	if a == b:
		print(0)
	else:
		an = a.count(1)
		bn = b.count(1)
		if an == bn:
			print(1)
		else:
			c = [a[i] - b[i] for i in range(n)]
			if n - c.count(0) == abs(an - bn):
				print(abs(an - bn))
			else:
				print(abs(an - bn) + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	o = a.count(1)
	o1 = b.count(1)
	ans = abs(o1 - o)
	k = ans
	for i in range(n):
		if a[i] != b[i] and k > 0:
			k -= 1
			a[i] = b[i]
	if a != b:
		ans += 1
	print(ans)


for i in range(int(input())):
	c = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if a == b:
		print(0)
	else:
		d = abs(a.count(1) - b.count(1)) + 1
		e = 0
		for i in range(c):
			if a[i] != b[i]:
				e += 1
		print(min(d, e))


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, b, n):
	if a == b:
		return 0
	(ca, cb) = (a.count(1), b.count(1))
	if ca == cb:
		return 1
	if ca < cb:
		(a, b) = (b, a)
		(ca, cb) = (cb, ca)
	cc = len([i for i in range(n) if a[i] != b[i]])
	if ca - cb == cc:
		return cc
	return ca - cb + 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solve(a, b, n))


t = int(input())
for tc in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	cumulDiff = abs(sum(a) - sum(b))
	indivDiff = 0
	for i in range(n):
		if a[i] != b[i]:
			indivDiff += 1
	if indivDiff > cumulDiff:
		print(cumulDiff + 1)
	else:
		print(indivDiff)


T = int(input())
while T:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = abs(sum(a) - sum(b)) + 1
	count = 0
	for i in range(n):
		if a[i] != b[i]:
			count += 1
	ans = min(ans, count)
	print(ans)
	T -= 1


n = int(input())
for sdfjlsd in range(n):
	length = int(input())
	a = input().split()
	b = input().split()
	different = False
	difference = 0
	dicta = {'0': 0, '1': 0}
	dictb = {'0': 0, '1': 0}
	for index in range(length):
		if a[index] != b[index]:
			different = True
			difference += 1
		dicta[a[index]] += 1
		dictb[b[index]] += 1
	if not different:
		print(0)
		continue
	changed_times = difference
	value = abs(dictb['1'] - dicta['1']) + 1
	print(min(value, changed_times))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	asum = sum(a)
	bsum = sum(b)
	unequal = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			unequal += 1
	if unequal == 0:
		print(0)
	elif abs(asum - bsum) == unequal:
		print(unequal)
	else:
		print(min(1 + abs(asum - bsum), unequal))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	tot = 0
	for i in range(n):
		if a[i] != b[i]:
			tot += 1
	if tot == 0:
		print(0)
	else:
		print(min(tot, abs(sum(a) - sum(b)) + 1))


for aa in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = 0
	y = 0
	c = 0
	d = 0
	for i in a:
		if i == 1:
			x += 1
		if i == 0:
			y += 1
	for i in b:
		if i == 1:
			c += 1
		if i == 0:
			d += 1
	s = min(abs(x - c), abs(y - d)) + 1
	s2 = 0
	for i in range(n):
		if a[i] != b[i]:
			s2 += 1
	print(min(s, s2))


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	rewrite_count = abs(a.count(0) - b.count(0))
	different_positions = sum((1 if x != y else 0 for (x, y) in zip(a, b)))
	if rewrite_count == different_positions:
		return rewrite_count
	else:
		return rewrite_count + 1
t = int(input())
for _ in range(t):
	print(solve())