Timur initially had a binary string$^{\dagger}$ $s$ (possibly of length $0$). He performed the following operation several (possibly zero) times:

Add ${0}$ to one end of the string and ${1}$ to the other end of the string. For example, starting from the string ${1011}$, you can obtain either ${{0}}{1011}{{1}}$ or ${{1}}{1011}{{0}}$.

You are given Timur's final string. What is the length of the shortest possible string he could have started with?

$^{\dagger}$ A binary string is a string (possibly the empty string) whose characters are either ${0}$ or ${1}$.


-----Input-----

The first line of the input contains an integer $t$ ($1 \leq t \leq 100$) — the number of testcases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2000$) — the length of Timur's final string.

The second line of each test case contains a string $s$ of length $n$ consisting of characters ${0}$ or ${1}$, denoting the final string.


-----Output-----

For each test case, output a single nonnegative integer — the shortest possible length of Timur's original string. Note that Timur's original string could have been empty, in which case you should output $0$.


-----Examples-----

Input
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
Output
1
2
5
0
3
1
0
2
4


-----Note-----

In the first test case, the shortest possible string Timur started with is ${0}$, and he performed the following operation: ${0} \to {{1}}{0}{{0}}$.

In the second test case, the shortest possible string Timur started with is ${11}$, and he performed the following operation: ${11} \to {{0}}{11}{{1}}$.

In the third test case, the shortest possible string Timur started with is ${10101}$, and he didn't perform any operations.

In the fourth test case, the shortest possible string Timur started with is the empty string (which we denote by $\varepsilon$), and he performed the following operations: $\varepsilon \to {{1}}{}{{0}} \to {{0}}{10}{{1}} \to {{1}}{0101}{{0}}$.

In the fifth test case, the shortest possible string Timur started with is ${101}$, and he performed the following operations: ${101} \to {{0}}{101}{{1}} \to {{1}}{01011}{{0}}$.

Source: codeforces | Difficulty: EASY
Tags: Amortized analysis

Implementation


Solutions:
def pend(arr, size):
	if size > 1:
		left = 0
		right = size - 1
		while left < right:
			if arr[left] != arr[right]:
				size -= 2
			else:
				break
			left += 1
			right -= 1
	print(size)
tests = int(input())
for _ in range(tests):
	size = int(input())
	lists = list(input())
	pend(lists, size)


def counter():
	elements = int(input())
	a = input()
	if len(a) == elements:
		beg = 0
		end = -1
		for i in range(len(a) // 2):
			if a[beg] != a[end]:
				beg += 1
				end -= 1
			else:
				if beg > 0:
					print(len(a[beg:end + 1]))
				else:
					print(len(a))
				break
		if beg == len(a) // 2 and len(a) % 2 > 0:
			print(1)
		elif beg == len(a) // 2 and len(a) % 2 == 0:
			print(0)
t = int(input())
for i in range(t):
	counter()


def solve():
	n = int(input())
	s = input()
	(l, r) = (0, n - 1)
	while l <= r and s[l] != s[r]:
		l += 1
		r -= 1
	print(r - l + 1)
t = int(input())
for _ in range(t):
	solve()


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


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	s = input()
	ele = 0
	l = 0
	r = n - 1
	while True:
		if l >= r:
			break
		if s[l] == s[r]:
			break
		ele += 1
		l += 1
		r -= 1
	print(n - 2 * ele)


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
import heapq
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	while j > i and s[i] != s[j]:
		i += 1
		j -= 1
	if i == j:
		print(1)
	elif i > j:
		print(0)
	else:
		print(j - i + 1)
t = int(input())
while t != 0:
	solve()
	t -= 1


for t in range(int(input())):
	n = int(input())
	s = str(input())
	l = 0
	r = int(n - 1)
	while l < r and s[l] != s[r]:
		l += 1
		r -= 1
	print(r - l + 1)


def shortestInitial(nums):
	count = 0
	left = 0
	right = len(nums) - 1
	while left < right:
		if nums[left] != nums[right]:
			left += 1
			right -= 1
			count += 2
		else:
			return len(nums) - count
	return len(nums) - count
case = int(input())
for i in range(case):
	length = input()
	pos = input()
	print(shortestInitial(pos))


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		ans = n
		for i in range(n // 2):
			if s[i] == '0' and s[n - 1 - i] == '1':
				ans -= 2
			elif s[i] == '1' and s[n - 1 - i] == '0':
				ans -= 2
			else:
				break
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	a = input()
	i = 0
	j = n - 1
	while i <= j and a[i] != a[j]:
		i += 1
		j -= 1
	print(j - i + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	while i < j:
		if s[i] != s[j]:
			i += 1
			j -= 1
		else:
			break
	print(j - i + 1)


import sys

def in_int():
	return int(sys.stdin.readline())

def in_str():
	return sys.stdin.readline().rstrip()

def in_map_int():
	return map(int, sys.stdin.readline().split())

def in_arr_int():
	return list(map(int, sys.stdin.readline().split()))

def in_arr_str():
	return sys.stdin.readline().split()

def solve(n, s):
	(l, r) = (0, n - 1)
	while l < r:
		if s[l] != s[r]:
			l += 1
			r -= 1
		else:
			break
	return r - l + 1

def main():
	t = in_int()
	for _ in range(t):
		n = in_int()
		s = in_str()
		print(solve(n, s))
main()


import sys, os
TC = True

def solve():
	n = int(input())
	s = input()
	l = 0
	r = n - 1
	for i in range(n // 2):
		if s[i] == '0' and s[r] == '1' or (s[i] == '1' and s[r] == '0'):
			l += 1
			r -= 1
		else:
			break
	print(r - l + 1)
if os.path.exists('input.txt'):
	debug = True
	sys.stdin = open('input.txt', 'r')
if TC:
	for _ in range(int(input())):
		solve()
else:
	solve()


for _ in range(int(input())):
	a = int(input())
	k = a
	s = input()
	for i in range(a // 2):
		if s[i] == '0' and s[a - 1 - i] == '1' or (s[i] == '1' and s[a - 1 - i] == '0'):
			k -= 2
		else:
			break
	print(k)


def decrease(s, n):
	(x, y) = (0, n - 1)
	while x < y and (s[x] == '0' and s[y] == '1' or (s[x] == '1' and s[y] == '0')):
		x += 1
		y -= 1
	return s[x:y + 1]
for _ in range(int(input())):
	n = int(input())
	s = input()
	v = decrease(s, n)
	print(len(v))


n = int(input())
for i in range(n):
	m = int(input())
	st = input()
	l = 0
	r = m - 1
	total = m
	while l < r:
		if st[l] != st[r]:
			total -= 2
			l += 1
			r -= 1
		else:
			break
	print(total)


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


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


import sys
input = sys.stdin.readline

def solve_c():
	answ = 0
	n = int(input())
	s = list(input().strip())
	i = 0
	j = n - 1
	while i < j:
		if s[i] != s[j]:
			i += 1
			j -= 1
		else:
			break
	answ = j - i + 1
	return answ

def main():
	for _ in range(int(input())):
		answ = solve_c()
		print(answ)
main()


for _ in range(int(input())):
	length = int(input())
	(l, r) = (0, length - 1)
	string = input()
	while l < r and string[l] != string[r]:
		l += 1
		r -= 1
	print(r - l + 1)


rng = int(input())

def bin_find(n, binary):
	s = 0
	e = n - 1
	ctr = 0
	while s < e:
		if binary[s] == binary[e]:
			break
		ctr += 1
		s += 1
		e -= 1
	print(n - ctr * 2)
for i in range(rng):
	n = int(input())
	b = input()
	bin_find(n, b)


def swap(list, i1, i2):
	num = list[i1]
	list[i1] = list[i2]
	list[i2] = num
for _ in range(int(input())):
	a = int(input())
	b = input()
	count = 0
	for i in range(a // 2):
		if b[i] != b[a - 1 - i]:
			count += 1
		else:
			break
	print(a - 2 * count)


test = int(input())
for _ in range(test):
	length = int(input())
	binary = list(input())
	(left, right) = (0, length - 1)
	while left < right:
		if binary[right] != binary[left]:
			right -= 1
			left += 1
		else:
			break
	print(right - left + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	m = n // 2
	p = 0
	for i in range(m):
		if s[i] == '0' and s[n - 1 - i] == '1':
			p += 2
		elif s[i] == '1' and s[n - 1 - i] == '0':
			p += 2
		else:
			break
	print(n - p)


def exe():
	if n % 2 == 0:
		s1 = s[:n // 2]
		s2 = s[n - 1:n // 2 - 1:-1]
		cnt = n
		for i in range(n // 2):
			if s1[i] == '0' and s2[i] == '1':
				cnt -= 2
			elif s2[i] == '0' and s1[i] == '1':
				cnt -= 2
			else:
				break
		return cnt
	else:
		s1 = s[:n // 2]
		s2 = s[n - 1:n // 2:-1]
		cnt = n
		for i in range(n // 2):
			if s1[i] == '0' and s2[i] == '1':
				cnt -= 2
			elif s2[i] == '0' and s1[i] == '1':
				cnt -= 2
			else:
				break
		return cnt
for i in range(int(input())):
	n = int(input())
	s = input()
	print(exe())


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


t = int(input())
for _ in range(t):
	n = int(input())
	S = input()
	f = n - 1
	res = n
	for i in range(n // 2):
		if S[i] == '1' and S[f - i] == '0':
			res -= 2
		elif S[i] == '0' and S[f - i] == '1':
			res -= 2
		else:
			break
	print(res)


def shortest_string(n, s):
	operations = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			operations += 1
		else:
			break
	return n - 2 * operations
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(shortest_string(n, s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	p1 = 0
	p2 = n - 1
	while p1 < p2:
		if s[p1] == '0' and s[p2] == '1' or (s[p1] == '1' and s[p2] == '0'):
			p1 += 1
			p2 -= 1
		else:
			break
	print(p2 - p1 + 1)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	seq = list(input())
	left = 0
	right = n - 1
	got = False
	while left <= right:
		if seq[left] == seq[right]:
			print(right - left + 1)
			got = True
			break
		else:
			left += 1
			right -= 1
	if not got:
		print(0)


def pd(n, s):
	c = n
	for i in range(n // 2):
		if s[i] == '0' and s[n - i - 1] == '1' or (s[i] == '1' and s[n - i - 1] == '0'):
			c -= 2
		else:
			break
	return c
t = int(input())
a = []
for i in range(t):
	n = int(input())
	s = input()
	a.append(pd(n, s))
for i in a:
	print(i)


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]:
			break
		else:
			c += 2
	print(n - c)


test = int(input())
for _ in range(test):
	size = int(input())
	string = input()
	left_pointer = 0
	right_pointer = size - 1
	while left_pointer <= right_pointer:
		if string[left_pointer] == '0' and string[right_pointer] == '1':
			left_pointer += 1
			right_pointer -= 1
		elif string[left_pointer] == '1' and string[right_pointer] == '0':
			left_pointer += 1
			right_pointer -= 1
		else:
			print(right_pointer - left_pointer + 1)
			break
	if left_pointer > right_pointer:
		print(0)


def main():
	for t in range(int(input())):
		n = int(input())
		s = input()
		p1 = 0
		p2 = n - 1
		flag = False
		while p1 < p2:
			if s[p1] == s[p2]:
				ans = p2 - p1 + 1
				print(ans)
				flag = True
				break
			p1 += 1
			p2 -= 1
		if not flag:
			print(p2 - p1 + 1)
main()


t = int(input())
for i in range(t):
	l = int(input())
	s = input()
	ct = 0
	lim = l // 2
	res = 0
	if l % 2 != 0:
		res = 1
	for i in range(0, lim):
		pt2 = l - i - 1
		if (s[i], s[pt2]) == ('0', '1') or (s[i], s[pt2]) == ('1', '0'):
			pt2 -= 1
			ct += 1
		else:
			res = l - 2 * ct
			break
	print(res)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	n = inp()
	nums = insr()
	(i, j) = (0, len(nums) - 1)
	while nums[i] != nums[j] and i <= j:
		i += 1
		j -= 1
	print(j - i + 1)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	finalString = list(sys.stdin.readline().strip())
	while finalString[0] != finalString[-1]:
		del finalString[0]
		del finalString[-1]
		if len(finalString) == 0:
			break
	if len(finalString) == 0:
		print(0)
	else:
		print(len(finalString))


dd = int(input())
for i in range(dd):
	ww = int(input())
	cyma = ww
	f = str(input())
	kol = 0
	if ww % 2 == 0:
		for i in range(ww // 2):
			if f[ww - 1] != f[kol]:
				kol += 1
				ww -= 1
			else:
				break
	else:
		for i in range((ww - 1) // 2):
			if f[ww - 1] != f[kol]:
				kol += 1
				ww -= 1
			else:
				break
	print(cyma - kol * 2)


def solve(n, s):
	res = n
	count = 0
	i = 0
	while i < n // 2:
		if s[i] != s[n - i - 1]:
			count += 1
		else:
			break
		i = i + 1
	return res - 2 * count
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = input().strip()
	print(solve(n, s))


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


n = int(input())
ans = list()
for i in range(n):
	k = int(input())
	a = k
	curr = input()
	for i in range(k // 2):
		if curr[i] != curr[-1 - i]:
			a -= 2
		else:
			break
	ans.append(a)
for i in ans:
	print(i)


def fnc(a):
	i = 0
	while (a[i] == '0' and a[-i - 1] == '1' or (a[i] == '1' and a[-1 - i] == '0')) and 2 * i + 1 < n:
		i = i + 1
	return len(a) - 2 * i
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	print(fnc(a))


t = int(input())
while t:
	n = int(input())
	s = str(input())
	l = len(s) - 1
	co = 0
	for c in range(l // 2 + 1):
		if s[c] == s[l - c]:
			print(l - co + 1)
			break
		else:
			co += 2
	else:
		print(l - co + 1)
	t -= 1


def f(n, s):
	k = n
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			k -= 2
		else:
			return k
	return k
for t in range(int(input())):
	n = int(input())
	s = input()
	print(f(n, s))


for t in range(int(input())):
	n = int(input())
	s = input()
	p1 = 0
	p2 = n - 1
	while p2 > p1 and s[p1] != s[p2]:
		p1 += 1
		p2 -= 1
	print(p2 - p1 + 1)


def appen():
	n = int(input())
	s = input()
	a = int(n)
	k = int(0)
	p = int(n - 1)
	while k <= p:
		if s[k] == '0' and s[p] == '1' or (s[k] == '1' and s[p] == '0'):
			a -= 2
			k += 1
			p -= 1
		else:
			print(a)
			return
	print(a)
for _ in range(int(input())):
	appen()


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


test = int(input())
for _ in range(test):
	n = int(input())
	binary = input()
	if n < 2:
		print(n)
		continue
	left = 0
	right = n - 1
	length = n
	while left < right:
		if binary[left] == binary[right]:
			break
		else:
			length -= 2
			left += 1
			right -= 1
	print(length)


T = int(input())
for t in range(0, T):
	n = int(input())
	s = input()
	ptr1 = 0
	ptr2 = n - 1
	flag = 0
	while flag == 0 and ptr1 < ptr2:
		if s[ptr1] != s[ptr2]:
			ptr1 += 1
			ptr2 -= 1
		else:
			flag = 1
			break
	print(ptr2 - ptr1 + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	j = 0
	k = n - 1
	while j <= k:
		if s[j] != s[k]:
			j += 1
			k -= 1
		else:
			break
	if j == k:
		print(1)
	elif j < k:
		print(k - j + 1)
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = input()
	beg = 0
	end = n - 1
	while beg < end:
		if nums[beg] != nums[end]:
			beg += 1
			end -= 1
		else:
			break
	print(end - beg + 1)


import sys
num = int(sys.stdin.readline())
for line in range(num):
	length = int(sys.stdin.readline())
	string = sys.stdin.readline()
	i = 0
	j = length - 1
	while True:
		if j < i:
			print(0)
			break
		if string[i] == '0' and string[j] == '1' or (string[j] == '0' and string[i] == '1'):
			i += 1
			j -= 1
		else:
			print(j - i + 1)
			break


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


for i in range(int(input())):
	n = int(input())
	a = input()
	x = n // 2
	ans = 0
	for i in range(x):
		if a[i] == '0' and a[n - 1 - i] == '1' or (a[i] == '1' and a[n - 1 - i] == '0'):
			ans += 1
		else:
			break
	print(n - 2 * ans)


for _ in range(int(input())):
	(n, s) = (int(input()), input())
	(l, r) = (0, n - 1)
	while l < r:
		if s[l] == s[r]:
			break
		l += 1
		r -= 1
	if l == r:
		print(1)
	elif l > r:
		print(0)
	else:
		print(r - l + 1)


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


def check():
	input()
	d = input()
	if len(d) == 0:
		print(0)
		return
	while d[0] != d[-1]:
		d = d[1:-1]
		if len(d) == 0:
			print(0)
			return
	print(len(d))
	return

def main():
	n = int(input())
	for i in range(n):
		check()
main()


inputs_num = int(input())
for _ in range(inputs_num):
	length = int(input())
	if length == 0:
		print(0)
		continue
	if length == 1:
		input()
		print(1)
		continue
	bitnum = input()
	broke = False
	for i in range(length // 2):
		if bitnum[i] == bitnum[length - i - 1]:
			broke = True
			break
	if not broke:
		i += 1
	print(length - 2 * i)


for i in range(int(input())):
	n = int(input())
	a = input()
	c = 0
	s = n
	for z in range(n // 2 + n % 2):
		if a[z] == '0' and a[-1 - z] == '1' or (a[z] == '1' and a[-1 - z] == '0'):
			s -= 2
		else:
			c += 1
			print(s)
			break
	if c == 0:
		print(0)


def main():
	t = int(input())
	for _ in range(t):
		res = alg()
		print(res)

def alg():
	n = int(input())
	s = input()
	res = n
	for i in range(int(n / 2)):
		if s[i] == '0' and s[n - i - 1] == '1' or (s[i] == '1' and s[n - i - 1] == '0'):
			res -= 2
		else:
			break
	return res
main()


n = int(input())
for i in range(n):
	count = 0
	lent = int(input())
	binr = input()
	for i in range(lent // 2):
		if binr[i] == '1' and binr[lent - i - 1] == '0' or (binr[i] == '0' and binr[lent - i - 1] == '1'):
			count += 1
		else:
			break
	print(lent - 2 * count)


t = int(input())
for p in range(t):
	n = int(input())
	a = input()
	flag = 0
	for i in range(0, n // 2):
		if a[i] == a[n - i - 1]:
			flag = 1
			print(n - 2 * i)
			break
	if flag == 0:
		if n % 2 == 0:
			print(0)
		else:
			print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	while n >= 0:
		if n == 0:
			print('0')
			break
		elif s[0] != s[-1]:
			n -= 2
			s = s[1:-1]
		else:
			print(n)
			break


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	c = n
	for k in range(n // 2):
		if s[i] == '1' and s[j] == '0' or (s[i] == '0' and s[j] == '1'):
			i += 1
			j -= 1
			c -= 2
		elif i >= j:
			break
		else:
			break
	print(c)


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


t = int(input())
for _ in range(0, t):
	n = int(input())
	s = input()
	if n % 2 == 1:
		last = n // 2 - 1
		min = 1
	else:
		last = n // 2 - 1
		min = 0
	c = 0
	flag = -1
	for i in range(0, last + 1):
		if s[i] == '0' and s[n - i - 1] == '1':
			c += 1
		elif s[i] == '1' and s[n - i - 1] == '0':
			c += 1
		else:
			flag = n - i - 1 - i + 1
			break
	if n % 2 == 1:
		if flag == -1:
			print(1)
		else:
			print(flag)
	elif flag == -1:
		print(0)
	else:
		print(flag)


test = int(input())
for t in range(test):
	sz = int(input())
	inp = input()
	cnt = 0
	for i in range(0, int(sz / 2)):
		if inp[i] == '0' and inp[sz - i - 1] == '1' or (inp[i] == '1' and inp[sz - i - 1] == '0'):
			cnt += 2
		else:
			break
	print(sz - cnt)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	l = 0
	r = n - 1
	ans = n
	while l <= r:
		if s[l] == '0' and s[r] == '1' or (s[l] == '1' and s[r] == '0'):
			ans -= 2
			l += 1
			r -= 1
		else:
			print(ans)
			break
	if ans == 0:
		print(ans)


for s in [*open(0)][2::2]:
	i = 0
	j = len(s) - 2
	while (i < j) & (s[i] != s[j]):
		i += 1
		j -= 1
	print(j - i + 1)


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


def PrependAndAppend(n, s):
	(a, b) = (0, n - 1)
	result = n
	while a <= b:
		if s[a] == '1' and s[b] == '0' or (s[a] == '0' and s[b] == '1'):
			result -= 2
			a += 1
			b -= 1
		else:
			return result
	return result
t = int(input())
while t > 0:
	n = int(input())
	s = input()
	ans = PrependAndAppend(n, s)
	print(ans)
	t = t - 1


n = int(input())
for i in range(n):
	m = int(input())
	a = list(input())
	x = 0
	for i in range(m // 2):
		if a[i] == a[m - i - 1]:
			x += m - 2 * i
			break
	if x == 0:
		if m % 2 == 0:
			print(0)
		else:
			print(1)
	else:
		print(x)


tst = int(input())
for i in range(tst):
	num = int(input())
	s = input()
	l = num
	for j in range(num // 2):
		if s[j] == '0' and s[num - j - 1] == '1':
			l = l - 2
		elif s[j] == '1' and s[num - j - 1] == '0':
			l = l - 2
		else:
			break
	print(l)


cases = int(input())
for i in range(cases):
	n = int(input())
	arr = input()
	c = n
	if len(arr) <= 1:
		c = -1
		print(len(arr))
	else:
		for i in range(n // 2):
			if arr[i] == '0' and arr[n - i - 1] == '1' or (arr[i] == '1' and arr[n - i - 1] == '0'):
				c -= 2
			else:
				print(c)
				c = -1
				break
	if c != -1:
		print(c)


t = int(input())

def solve():
	n = int(input())
	s = input()
	nCopy = n
	if n < 2:
		return n
	ans = 0
	pointerLeft = 0
	pointerRight = n - 1
	while nCopy > 1:
		if s[pointerLeft] == '1' and s[pointerRight] == '0' or (s[pointerRight] == '1' and s[pointerLeft] == '0'):
			ans += 1
			pointerLeft += 1
			pointerRight -= 1
		nCopy -= 2
	return n - ans * 2
for _ in range(t):
	print(solve())


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	x = 0
	y = n - 1
	while x < y:
		if s[x] != s[y]:
			x += 1
			y -= 1
		else:
			break
	print(y - x + 1)


for i in range(int(input())):
	a = int(input())
	b = input()
	c = len(b)
	for i in range(c):
		if b[i] == b[c - (i + 1)]:
			break
		elif a == 0:
			break
		else:
			a -= 2
	print(a)


def gopi(n, mad):
	g = n
	pav = []
	pav[:0] = mad
	for i in range(g // 2):
		if pav[i] != pav[g - i - 1]:
			n = n - 2
		else:
			return n
	return n
for _ in range(int(input())):
	n = int(input())
	pav = input()
	print(gopi(n, pav))


t = int(input())
for i in range(t):
	tc = int(input())
	inp = input()
	x = 0
	for j in range(tc // 2):
		if inp[j] != inp[-(j + 1)]:
			x += 2
		else:
			break
	print(tc - x)


t = int(input())
for _ in range(t):
	l = int(input())
	res = l
	s = input()
	for i in range(l // 2):
		if s[i] != s[l - 1 - i]:
			res -= 2
		else:
			break
	print(res)


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	s = input().strip()
	l = 0
	r = n - 1
	while l < r and s[l] != s[r]:
		l += 1
		r -= 1
	print(n - l - (n - r - 1))


a = int(input())
for i in range(a):
	b = int(input())
	s = input()
	while len(s) > 1:
		if s[0] != s[-1]:
			s = s[1:-1]
		else:
			break
	print(len(s))


def prepend(n, s):
	l = 0
	r = n - 1
	ct = n
	while l <= r:
		if s[l] == '1' and s[r] == '0' or (s[l] == '0' and s[r] == '1'):
			ct -= 2
			l += 1
			r -= 1
		else:
			break
	return ct
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(prepend(n, s))


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	result = 0
	while i <= j:
		if s[i] == s[j]:
			result = j - i + 1
			break
		i += 1
		j -= 1
	if result == 0 and n % 2 == 1:
		result = 1
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	f = 0
	l = -1
	x = n
	if n % 2 == 0:
		for i in range(n // 2):
			if s[i] == '0' and s[l] == '1':
				l -= 1
				x -= 2
			elif s[i] == '1' and s[l] == '0':
				l -= 1
				x -= 2
			else:
				break
	else:
		for i in range(n // 2):
			if s[i] == '0' and s[l] == '1':
				l -= 1
				x -= 2
			elif s[i] == '1' and s[l] == '0':
				l -= 1
				x -= 2
			else:
				break
	print(x)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	ans = n
	for i in range(n // 2):
		if s[i] == s[-i - 1]:
			break
		else:
			ans -= 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	flag = False
	for i in range(n // 2):
		if s[i] == s[n - 1 - i]:
			x = (n // 2 - i) * 2
			if n % 2 == 1:
				x += 1
			print(x)
			flag = True
			break
	if flag == False:
		if n % 2 == 1:
			print(1)
		else:
			print(0)


for i in range(int(input())):
	n = int(input())
	s = input()
	p1 = 0
	p2 = n - 1
	while p1 < p2:
		if s[p1] != s[p2]:
			p1 += 1
			p2 -= 1
		else:
			break
	print(p2 - p1 + 1)


t = int(input())
for _ in range(t):
	l = int(input())
	s = input()
	x = s[::-1]
	ans = 0
	cont = 0
	limit = 0
	j = 0
	if s[0] == x[0]:
		print(l)
	else:
		j = l - 1
		if l % 2 == 0:
			limit = int(l / 2)
		else:
			limit = int((l - 1) / 2)
		for i in range(limit):
			if s[i] != s[j]:
				cont += 1
			else:
				break
			j = j - 1
		ans = l - 2 * cont
		print(int(l - 2 * cont))


for i in range(int(input())):
	n = int(input())
	k = input()
	l = []
	for i in range(n // 2):
		if k[i] != k[n - i - 1]:
			l.append(n - 2 * i - 2)
		else:
			break
	if len(l) == 0:
		print(len(k))
	else:
		print(l[-1])


for i in range(int(input())):
	a = int(input())
	b = input()
	b = list(b)
	c = 0
	while b != []:
		if b[0] == '0' and b[-1] == '1' or (b[0] == '1' and b[-1] == '0'):
			b.remove(b[0])
			b.pop()
		else:
			break
	c = len(b)
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = 0
	h = len(s) - 1
	c = 0
	if n % 2 == 0:
		while l < h:
			if s[l] != s[h]:
				l += 1
				h -= 1
				c += 1
			else:
				break
		print(n - c * 2)
	else:
		while l < h:
			if s[l] != s[h]:
				l += 1
				h -= 1
				c += 1
			else:
				break
		print(n - c * 2)


t = int(input())
for i in range(t):
	n = int(input())
	m = input()
	m = list(m)
	while len(m) > 0:
		if m[0] == '1' and m[-1] == '0':
			m.pop()
			del m[0]
		elif m[0] == '0' and m[-1] == '1':
			m.pop()
			del m[0]
		else:
			break
	print(len(m), end='\n')