You are given a binary string A of length N.

You can perform the following type of operation on the string A:
Choose two different indices i and j (1≤ i,j≤ N);
Change A_{i} and A_{j} to A_{i} \oplus A_{j}. Here \oplus represents the [bitwise XOR] operation.

Find the minimum number of operations required to convert the given string into a [palindrome].

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

- First line of the input contains T, the number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the size of the string.
- Second line of each test case contains a binary string A of length N containing 0s and 1s only.

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

For each test case, print the minimum number of operations required to make the string a palindrome.

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

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

----- Sample Input 1 ------ 
4
5
11011
7
0111010
1
1
4
1100
----- Sample Output 1 ------ 
0
1
0
1
----- explanation 1 ------ 
Test Case $1$ :  The given string $11011$ is already a palindrome. So, no operation is required. The answer for the case is $0$.

Test Case $2$ : The given string $0111010$ is not a palindrome. 
- Choose the indices $i=3$ and $j=5$. Now, $A_{3} \oplus A_{5} = 1\oplus 0 = 1$. Thus, we set $A_{3}$ and $A_{5}$ equal to $1$.

After the operation, the resulting string is $0111110$ which is a palindrome. The number of operations required is $1$.

Test Case $3$ :  The given string $1$ is already a palindrome. So, no operation is required. The answer for the case is $0$.

Test Case $4$ : The given string $1100$ is not a palindrome. 
- Choose the indices $i=1$ and $j=2$. Now, $A_{1} \oplus A_{2} = 1\oplus 1 = 0$. Thus, we set $A_{1}$ and $A_{2}$ equal to $0$.

After the operation, the resulting string is $0000$ which is a palindrome. The number of operations required is $1$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

String algorithms

Greedy algorithms

Mathematics

Data structures


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
		next
	else:
		diff = [int(s[i] == s[-(i + 1)]) for i in range(len(s) // 2)]
		print(-(-diff.count(0) // 2))


for i in range(int(input())):
	n = int(input())
	a = input()
	c = 0
	for i in range(n // 2):
		if a[i] != a[n - 1 - i]:
			c += 1
	print((c + 1) // 2)


n = int(input())
for i in range(n):
	k = int(input())
	k1 = input()
	s = 0
	for i in range(k // 2):
		if k1[i] != k1[k - i - 1]:
			s += 1
	if s % 2 == 0:
		print(s // 2)
	else:
		print(1 + s // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	i = 0
	j = n - 1
	s = 0
	while i < j:
		if a[i] != a[j]:
			s = s + 1
		i = i + 1
		j = j - 1
	print((s + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			ans += 1
	if ans % 2 == 0:
		print(ans // 2)
	else:
		print(1 + ans // 2)


n = int(input())
for i in range(n):
	x = int(input())
	a = input()
	i = 0
	j = len(a) - 1
	s = 0
	while i < j:
		if a[i] != a[j]:
			s += 1
		i += 1
		j -= 1
	print((s + 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	s = 0
	j = 0
	w = n - 1
	while j <= w:
		if st[j] != st[w]:
			s = s + 1
		j += 1
		w = w - 1
	print((s + 1) // 2)


for _ in range(int(input())):
	t = int(input())
	a = input()
	if a == a[::-1]:
		print(0)
		next
	else:
		diff = [int(a[i] == a[-(i + 1)]) for i in range(len(a) // 2)]
		print(-(-diff.count(0) // 2))


for i in range(int(input())):
	size = int(input())
	stop = size // 2 if size % 2 == 0 else (size - 1) // 2
	input_string = input()
	operations = 0
	for j in range(stop):
		if input_string[j] != input_string[size - 1 - j]:
			operations += 1
	result = operations // 2 if operations % 2 == 0 else (operations + 1) // 2
	print(result)


for i in range(int(input())):
	value = int(input())
	a = input()
	s = a[::-1]
	m = []
	if a == s:
		print('0')
	else:
		for i in range(value // 2):
			if a[i] != s[i]:
				m.append(0)
		if m.count(0) % 2 != 0:
			print(m.count(0) // 2 + 1)
		else:
			print(m.count(0) // 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	x = s[::-1]
	m = []
	if x == s:
		print(0)
	else:
		for i in range(n // 2):
			if s[i] != x[i]:
				m.append(0)
		if m.count(0) % 2 != 0:
			print(m.count(0) // 2 + 1)
		else:
			print(m.count(0) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	d = []
	if s == s[::-1]:
		print(0)
	else:
		for i in range(len(s) // 2):
			d.append(int(s[i] == s[-(i + 1)]))
		if d.count(0) % 2 != 0:
			print(d.count(0) // 2 + 1)
		else:
			print(d.count(0) // 2)


for i in range(int(input())):
	N = int(input())
	Str = input()
	ans = 0
	for i in range(N // 2):
		if Str[i] != Str[N - i - 1]:
			ans += 1
	if ans % 2 == 0:
		print(ans // 2)
	else:
		print(ans // 2 + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	(i, j) = (0, n - 1)
	count = 0
	while i < j:
		if s[i] != s[j]:
			count += 1
		i += 1
		j -= 1
	print((count + 1) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(i, j) = (0, n - 1)
	cnt = 0
	while i < j:
		if s[i] != s[j]:
			cnt += 1
		i += 1
		j -= 1
	print((cnt + 1) // 2)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	c = 0
	if s == s[::-1]:
		print(0)
	else:
		for i in range(int(n // 2)):
			if s[i] != s[n - 1 - i]:
				c += 1
		print((c + 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	count = 0
	if a == a[::-1]:
		print(0)
	else:
		for i in range(int(n // 2)):
			if a[i] != a[n - 1 - i]:
				count += 1
		print((count + 1) // 2)


tt = 1
tt = int(input())
for _ in range(tt):
	n = int(input())
	s = list(input())
	l = 0
	r = n - 1
	cnt = 0
	while l < r:
		if s[l] != s[r]:
			cnt += 1
		l += 1
		r -= 1
	print(cnt // 2 + cnt % 2)


n = int(input())
for i in range(n):
	n2 = int(input())
	s = input()
	s = list(s)
	c = 0
	for j in range(n2 // 2):
		if int(s[j]) ^ int(s[-(j + 1)]) == 1:
			c += 1
	if c % 2 == 0:
		print(c // 2)
	else:
		print(c // 2 + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	for j in range(n // 2):
		if int(s[j]) ^ int(s[-(j + 1)]) == 1:
			c = c + 1
	if c % 2 == 0:
		print(c // 2)
	else:
		print(c // 2 + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	x = 0
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			x += 1
	print(-(-x // 2))


t = int(input())
while t:
	n = int(input())
	s = input()
	s1 = s[::-1]
	c = 0
	if s == s1:
		print(0)
	else:
		for i in range(n // 2):
			if s[i] != s[n - i - 1]:
				c += 1
		print((c + 1) // 2)
	t -= 1


for item in range(int(input())):
	t = int(input())
	x = list(input())[:t]
	if x[:] == x[::-1]:
		print('0')
	else:
		k = 0
		for i in range(t // 2):
			if x[i] != x[t - i - 1]:
				k += 1
		print((k + 1) // 2)


t = int(input())
while t != 0:
	y = int(input())
	n = input()
	c = 0
	i = 0
	j = len(n) - 1
	while i < j:
		if n[i] == n[j]:
			i = i + 1
			j = j - 1
			continue
		else:
			c = c + 1
		i = i + 1
		j = j - 1
	print((c + 1) // 2)
	t = t - 1


r = int(input())
for i in range(0, r):
	d = int(input())
	s = input()
	p = s[::-1]
	if s == p:
		print(0)
		next
	else:
		diff = [int(s[i] == s[-(i + 1)]) for i in range(len(s) // 2)]
		print(-(-diff.count(0) // 2))


for i in range(int(input())):
	n = int(input())
	s = input()
	x = 0
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			x += 1
	if x <= 1:
		print(x)
	elif not x % 2:
		print(x // 2)
	else:
		print(x // 2 + 1)


import math as m
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			c += 1
	print(m.ceil(c / 2))


for i in range(int(input())):
	x = int(input())
	s = input()
	c = 0
	p = 0
	l = len(s) - 1
	while p < l:
		if s[p] != s[l]:
			c += 1
		p += 1
		l -= 1
	print((c + 1) // 2)


T = int(input())
for i in range(T):
	N = int(input())
	S = list(input())
	if N == 1:
		print(0)
	else:
		c = 0
		(P, P1) = (0, len(S) - 1)
		while P < P1:
			if S[P] != S[P1]:
				c += 1
			P += 1
			P1 -= 1
		print((c + 1) // 2)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	c = 0
	(l, r) = (0, len(s) - 1)
	while l < r:
		if s[l] != s[r]:
			c += 1
		l += 1
		r -= 1
	print((c + 1) // 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	(l, r) = (0, len(s) - 1)
	while l < r:
		if s[l] != s[r]:
			count += 1
		l += 1
		r -= 1
	print((count + 1) // 2)


def solve():
	n = int(input())
	s = input()
	count = 0
	(l, r) = (0, len(s) - 1)
	while l < r:
		if s[l] != s[r]:
			count += 1
		l += 1
		r -= 1
	return (count + 1) // 2
t = int(input())
while t:
	print(solve())
	t -= 1


for i in range(int(input())):
	k = int(input())
	s = input()
	c = 0
	for i in range(len(s) // 2):
		if s[i] != s[k - i - 1]:
			c += 1
	print(c // 2 + c % 2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	flag = 0
	if len(s) <= 1:
		print(0)
	else:
		for i in range(len(s) // 2):
			if s[i] != s[-i - 1]:
				flag = flag + 1
		print((flag + 1) // 2)


test = int(input())
for i in range(test):
	x = int(input())
	s = input()
	flag = 0
	if len(s) <= 1:
		print(0)
	else:
		for i in range(len(s) // 2):
			if s[i] != s[-i - 1]:
				flag = flag + 1
		print((flag + 1) // 2)


import math
for i in range(int(input())):
	n = int(input())
	a = input()
	s = a[::-1]
	c = 0
	if a == s:
		print(0)
	else:
		for k in range(math.ceil(n / 2)):
			if s[k] != a[k]:
				c += 1
		print(math.ceil(c / 2))


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n // 2):
		c += s[i] != s[-(i + 1)]
	print((c + 1) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	i = n // 2 - 1
	c = 0
	while i >= 0:
		if a[i] == a[n - i - 1]:
			i -= 1
			continue
		else:
			j = i - 1
			while j >= 0 and a[j] == a[n - j - 1]:
				j -= 1
			c += 1
			t = int(a[i]) ^ int(a[j])
			a = a[:i] + str(t) + a[i + 1:]
			a = a[:j] + str(t) + a[j + 1:]
			i = j - 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = len(s)
	if x % 2 == 0:
		a = s[:x // 2]
		b = s[x // 2:]
	else:
		a = s[:x // 2]
		b = s[x // 2 + 1:]
	b = b[::-1]
	c = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			c += 1
	print((c + 1) // 2)


import math
for t in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	a = s[::-1]
	if s == a:
		print(0)
	else:
		for i in range(math.ceil(len(s) / 2)):
			if s[i] != a[i]:
				count += 1
		print(math.ceil(count / 2))


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in range(n // 2):
		if s[i] != s[-(i + 1)]:
			count += 1
	print((count + 1) // 2)


import math
for t in range(int(input())):
	n = int(input())
	a = str(input())
	c = 0
	for i in range(int(n / 2)):
		if a[i] != a[n - i - 1]:
			c += 1
	print(math.ceil(c / 2))


import math
for i in range(int(input())):
	n = int(input())
	x = input()
	c = 0
	if x == x[::-1]:
		print(0)
	else:
		for i in range(n // 2):
			if x[i] == x[n - 1 - i]:
				c = c
			else:
				c += 1
		print(math.ceil(c / 2))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(input())
	x = a[::-1]
	c = 0
	for j in range(n):
		c += int(x[j] != a[j])
	c = c // 2
	print((c + 1) // 2)