You are given a palindromic string $s$ of length $n$.

You have to count the number of indices $i$ $(1 \le i \le n)$ such that the string after removing $s_i$ from $s$ still remains a palindrome.

For example, consider $s$ = "aba"

If we remove $s_1$ from $s$, the string becomes "ba" which is not a palindrome.

If we remove $s_2$ from $s$, the string becomes "aa" which is a palindrome.

If we remove $s_3$ from $s$, the string becomes "ab" which is not a palindrome.

A palindrome is a string that reads the same backward as forward. For example, "abba", "a", "fef" are palindromes whereas "codeforces", "acd", "xy" are not.


-----Input-----

The input consists of multiple test cases. The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^3)$  — the number of test cases. Description of the test cases follows.

The first line of each testcase contains a single integer $n$ $(2 \leq n \leq 10^5)$  — the length of string $s$.

The second line of each test case contains a string $s$ consisting of lowercase English letters. It is guaranteed that $s$ is a palindrome.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a single integer  — the number of indices $i$ $(1 \le i \le n)$ such that the string after removing $s_i$ from $s$ still remains a palindrome.


-----Examples-----

Input
3
3
aba
8
acaaaaca
2
dd
Output
1
4
2


-----Note-----

The first test case is described in the statement.

In the second test case, the indices $i$ that result in palindrome after removing $s_i$ are $3, 4, 5, 6$. Hence the answer is $4$.

In the third test case, removal of any of the indices results in "d" which is a palindrome. Hence the answer is $2$.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Greedy algorithms


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	if n == 1:
		print(1)
	elif n % 2 == 0:
		t = s[n // 2]
		i = n // 2 - 1
		while i >= 0 and s[i] == t:
			i -= 1
		i += 1
		print(n - i * 2)
	else:
		t = s[n // 2]
		i = n // 2
		while i >= 0 and s[i] == t:
			i -= 1
		i += 1
		print(n - i * 2)


for s in [*open(0)][2::2]:
	n = len(s) - 1
	print(n - 2 * len(s[n // 2:-1].lstrip(s[n // 2])))


for s in [*open(0)][2::2]:
	n = len(s) - 1
	print(n - 2 * len(s[n // 2:].strip(s[n // 2])) + 2)


for b in [*open(0)][2::2]:
	v = len(b) - 1
	print(v - 2 * len(b[v // 2:].strip(b[v // 2])) + 2)


for p in [*open(0)][2::2]:
	i = len(p) - 1
	print(i - 2 * len(p[i // 2:].strip(p[i // 2])) + 2)


for c in [*open(0)][2::2]:
	n = len(c) - 1
	print(n - 2 * len(c[n // 2:].strip(c[n // 2])) + 2)


for a in [*open(0)][2::2]:
	b = len(a) - 1
	print(b - 2 * len(a[b // 2:].strip(a[b // 2])) + 2)


for s in [*open(0)][2::2]:
	v = len(s) - 1
	print(v - 2 * len(s[v // 2:].strip(s[v // 2])) + 2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	c = s[n // 2]
	tot = n % 2
	for i in range(n // 2 - 1, -1, -1):
		if s[i] != c:
			break
		tot += 2
	print(tot)


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


def solve():
	n = int(input())
	s = input().strip()
	ans = 0
	for i in range(n // 2, 0, -1):
		if s[i] == s[i - 1]:
			ans += 2
		else:
			break
	return ans if len(s) % 2 == 0 else ans + 1
for _ in range(int(input())):
	print(solve())


k = int(input().strip())
store = [0] * k
for i in range(k):
	l = int(input().strip())
	st = input().strip()
	count = 0
	if l % 2 == 1:
		mid = int((l - 1) / 2)
		letter = st[mid]
		while st[mid - count] == letter and mid - count > -1:
			count += 1
		store[i] = (count - 1) * 2 + 1
	else:
		mid = int(l / 2) - 1
		letter = st[mid]
		while st[mid - count] == letter and mid - count > -1:
			count += 1
		store[i] = count * 2
for num in store:
	print(num)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	mid = (n - 1) // 2
	a = s[mid]
	count = 0
	while s[mid] == a and mid >= 0:
		count += 1
		mid -= 1
	if n % 2 == 0:
		print(count * 2)
	else:
		print(count * 2 - 1)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	s = list(input())
	if len(set(s)) == 1:
		print(n)
	else:
		cnt = 0
		if n % 2 != 0:
			a = s[n // 2]
			for i in range(n // 2 + 1):
				if s[n // 2 - i] == a:
					cnt += 1
				else:
					break
			print(2 * cnt - 1)
		else:
			cnt = 0
			a = s[n // 2 - 1]
			for i in range(n // 2):
				if s[n // 2 - i - 1] == a:
					cnt += 1
				else:
					break
			print(2 * cnt)
	t = t - 1


a = int(input())
for i in range(a):
	k = int(input())
	d = input()
	c = 0
	if len(set(d)) == 1:
		print(k)
	elif k % 2 == 1:
		d = d[:k // 2 + 1]
		d = d[::-1]
		for i in range(1, len(d)):
			if d[0] == d[i]:
				c += 1
			else:
				break
		print(c * 2 + 1)
	else:
		d = d[:k // 2]
		d = d[::-1]
		for i in range(1, len(d)):
			if d[0] == d[i]:
				c += 1
			else:
				break
		print(c * 2 + 2)


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


def solve():
	n = int(input())
	s = input()
	ans = 0
	if n % 2 == 0:
		for i in range(len(s) // 2 - 1, n - 1):
			if s[i] == s[i + 1]:
				ans += 1
			else:
				break
	else:
		for i in range(len(s) // 2, n - 1):
			if s[i] == s[i + 1]:
				ans += 1
			else:
				break
	ans *= 2
	if len(s) % 2 == 0:
		print(ans)
	else:
		print(ans + 1)
t = int(input())
while t > 0:
	solve()
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	x = input()
	if n == 2:
		print(2)
	else:
		a = math.floor((n + 1) / 2)
		y = x[:a][::-1]
		p = y[0]
		i = 1
		for k in y[1:]:
			if k == p:
				p = k
				i += 1
			else:
				break
		if n % 2 == 0:
			print(i * 2)
		else:
			print((i - 1) * 2 + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	if len(set(s)) == 1:
		d = n
	else:
		d = n % 2
		k = n // 2
		j = k - 1
		while s[j] == s[k]:
			d += 2
			j -= 1
	print(d)


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


def pal_ind(s):
	l = len(s)
	if l != 1:
		req_s = s[0:int((l + 1) / 2)]
		first = req_s[-1]
		cnt = 0
		for i in range(1, len(req_s) + 1):
			if req_s[-i] == first:
				cnt += 1
			else:
				break
		return cnt * 2 - l % 2
	else:
		return 0
ans_lst = []
for i in range(int(input())):
	l = int(input())
	string = input()
	ans_lst.append(pal_ind(string))
for i in ans_lst:
	print(i)


for i in range(int(input())):
	n = int(input())
	s = input()
	h = s[n // 2:]
	v = len(h) - len(h.lstrip(h[0]))
	print(v * 2 - n % 2)


times = int(input())
for time in range(times):
	n = int(input())
	string = input()
	if n % 2 == 1:
		k = 1
	else:
		k = 2
	h = n // 2
	c = string[h]
	for j in range(h + 1, n):
		if string[j] == c:
			k += 2
		else:
			break
	print(k)


def function(st):
	count = 0
	index = len(st) // 2
	for i in range(index, -1, -1):
		if st[index] == st[i]:
			count += 1
		else:
			break
	for i in range(index, len(st)):
		if st[index] == st[i]:
			count += 1
		else:
			break
	return count - 1
n = int(input())
for i in range(n):
	m = int(input())
	st = input()
	print(function(st))


def counter(a, b, c):
	count_r = 0
	for y in range(a + 1, b):
		if c[a] == c[y]:
			count_r += 1
		else:
			break
	return count_r
test = int(input())
for x in range(0, test):
	n = int(input())
	string_h = input()
	if n == 0:
		print(0)
	elif n % 2 != 0:
		k = int(n / 2)
		count = counter(k, n, string_h) * 2 + 1
	else:
		k = int(n / 2) - 1
		count = counter(k, n, string_h) * 2
	print(count)


for _ in range(int(input())):
	n = int(input())
	str1 = input()
	mid = n // 2
	i = mid
	char = str1[mid]
	while i < n and str1[i] == char:
		i += 1
	print((i - mid) * 2 if n % 2 == 0 else (i - mid) * 2 - 1)


t = int(input())

def get_count(s):
	n = len(s)
	if n % 2 == 0:
		count = 2
		mid = s[int(n / 2) - 1]
		i = int(n / 2) - 2
		while i >= 0 and s[i] == mid:
			count += 2
			i -= 1
		return count
	else:
		count = 1
		mid = s[int(n / 2)]
		i = int(n / 2) - 1
		while i >= 0 and s[i] == mid:
			count += 2
			i -= 1
		return count
	return 0
for _ in range(t):
	n = int(input())
	s = input()
	print(get_count(s))


for i in range(int(input())):
	(n, s) = (int(input()), input())
	c = s[n // 2]
	for i in range(n // 2, n):
		if s[i] != c:
			break
		else:
			i = n
	print(2 * i - n)


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
t = num_inp()
for _ in range(t):
	n = num_inp()
	s = str_inp()
	if len(set(s)) == 1 or n == 2:
		print(n)
	else:
		count = 0
		mid = n // 2 - 1
		val = s[n // 2]
		while mid != -1 and s[mid] == val:
			count += 1
			mid -= 1
		if n % 2 == 0:
			count *= 2
		else:
			count = 2 * count + 1
		print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if len(set(s)) == 1:
		print(n)
		continue
	a = s[n // 2]
	i = n // 2 + 1
	ans = 1
	if n % 2 == 0:
		ans = 2
	while s[i] == a:
		ans += 2
		i += 1
	print(ans)


def main():
	n = int(input())
	s = input()
	i = n // 2
	ans = 0
	while i < n and s[i] == s[n // 2]:
		i += 1
		ans += 1
	if n % 2 == 1:
		ans = ans * 2 - 1
	else:
		ans = ans * 2
	print(ans)
for _ in range(int(input())):
	main()


def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		string = input()
		mid = n // 2
		if n % 2 == 0:
			mid -= 1
			left = mid - 1
			right = mid + 1
			count1 = 0
			for i in range(left, -1, -1):
				if string[i] != string[mid]:
					break
				count1 += 1
			for i in range(right, n):
				if string[i] != string[mid]:
					break
				count1 += 1
			if count1 == 0:
				print(0)
			else:
				print(count1 + 1)
		else:
			left = mid - 1
			right = mid + 1
			count = 0
			for i in range(left, -1, -1):
				if string[i] != string[mid]:
					break
				count += 1
			for i in range(right, n):
				if string[i] != string[mid]:
					break
				count += 1
			if count == 0:
				print(1)
			else:
				print(count + 1)
main()


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


def solve():
	n = int(input())
	s = input()
	if len(s) == 2:
		print(2)
		return
	x = len(s) // 2
	c = 1
	for i in range(x + 1, n):
		if s[i] == s[x]:
			c += 1
		else:
			break
	if n % 2 == 0:
		print(2 * c)
	else:
		print(2 * c - 1)
t = int(input())
for i in range(t):
	solve()


for i in range(int(input())):
	lenn = int(input())
	string = input()
	ans = 0
	imp = string[lenn // 2]
	for i in string[:lenn // 2 + 1][::-1]:
		if i != imp:
			break
		else:
			ans += 1
	for i in string[lenn // 2 + 1:]:
		if i != imp:
			break
		else:
			ans += 1
	print(ans)


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


n_test_cases = int(input())
ans_arr = []
for i in range(n_test_cases):
	len_str = int(input())
	inp_str = input()
	if len_str % 2 == 0:
		count = 0
		middle_index = int(len_str / 2) - 1
		middle_char = inp_str[middle_index]
		while True:
			curr_index = middle_index + count + 1
			if curr_index == len_str:
				break
			if inp_str[curr_index] == middle_char:
				count += 1
			else:
				break
		ans_arr.append(count * 2)
	else:
		count = 0
		middle_index = int(len_str / 2)
		middle_char = inp_str[middle_index]
		while True:
			curr_index = middle_index + count + 1
			if curr_index == len_str:
				break
			if inp_str[curr_index] == middle_char:
				count += 1
			else:
				break
		ans_arr.append(count * 2 + 1)
for i in range(len(ans_arr)):
	print(ans_arr[i])


def pal(st):
	for i in range(len(st) // 2):
		if st[i] != st[len(st) - 1 - i]:
			return False
	return True
t = int(input())
for j in range(t):
	n = int(input())
	st = input()
	if st.count(st[0]) == len(st):
		print(len(st))
	else:
		k = 0
		if n % 2 != 0:
			ind = n // 2
			i = ind + 1
			k = 1
			while st[i] == st[ind]:
				k += 2
				i += 1
		else:
			ind = n // 2 - 1
			i = 1
			k = 2
			while st[ind - i] == st[ind + 1]:
				k += 2
				i += 1
		print(k)


t = int(input())
while t:
	n = int(input())
	s = input()
	ct = 0
	if n % 2 == 0:
		ct += 2
		idx = n // 2
		x = s[idx]
		for i in range(idx + 1, n):
			if s[i] == x:
				ct += 2
			else:
				break
	else:
		ct += 1
		idx = (n - 1) // 2
		x = s[idx]
		for i in range(idx + 1, n):
			if s[i] == x:
				ct += 2
			else:
				break
	print(ct)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	word = input()
	count = 0
	letter = word[n // 2]
	for i in range(n // 2, n - 1):
		if word[i] == letter and word[i + 1] != letter:
			index1 = i + 1
			break
	else:
		index1 = n
	print(n - (n - index1) * 2)


def main():
	n = int(input())
	s = input()
	i = (n - 1) // 2
	c = s[i]
	(l, r) = (i, i)
	while r < n and s[r] == c:
		r += 1
	while l >= 0 and s[l] == c:
		l -= 1
	return r - l - 1
t = int(input())
for _ in range(t):
	print(main())


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


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	m = 0
	if n % 2 == 0:
		mid = int(n // 2)
		s1 = s[:mid]
		s2 = s[mid:]
		s1 = s1[::-1]
		ch = s2[0]
		for j in range(len(s1)):
			if s1[j] == s2[j] and s1[j] == ch:
				m += 1
			else:
				break
	else:
		mid = int((n - 1) // 2)
		s1 = s[:mid]
		s2 = s[mid + 1:]
		s1 = s1[::-1]
		ch = s[mid]
		for j in range(len(s1)):
			if s1[j] == s2[j] and s1[j] == ch:
				m += 1
			else:
				break
	if n % 2 == 0:
		m *= 2
	else:
		m = m * 2 + 1
	print(m)


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


def main():
	n = int(input())
	for _ in range(n):
		input()
		s = input()
		print(solve(s))

def solve(s):
	(i, res) = (len(s) // 2, -(len(s) % 2))
	mid_char = s[i]
	while i < len(s) and s[i] == mid_char:
		i += 1
	res += 2 * (i - len(s) // 2)
	return res
main()


N = int(input())
for i in range(N):
	n = int(input())
	s = input()
	if n % 2:
		(l, r) = (n // 2, n // 2 + 1)
		pat = s[l]
	else:
		(l, r) = (n // 2, n // 2)
		pat = s[l]
	while r < n and pat == s[r]:
		l -= 1
		r += 1
	print(r - l)


t = int(input())
for z in range(t):
	ans = 0
	n = int(input())
	s = input()
	if n % 2 == 0:
		mid = int(n / 2)
	elif n % 2 == 1:
		mid = int(n // 2 + 1)
	k = s[mid - 1]
	for i in range(mid - 1, n):
		if s[i] == k:
			ans += 1
		elif s[i] != k:
			break
	if n % 2 == 0:
		print(2 * (ans - 1))
	elif n % 2 != 0:
		print(2 * ans - 1)


iT = int(input())
for _ in range(iT):
	iN = int(input())
	str_temp = input()
	i = 0
	cnt = 0
	x = iN // 2
	if iN % 2 == 1:
		cnt += 1
	for idx in range(x - 1, -1, -1):
		if str_temp[idx] == str_temp[x]:
			cnt += 2
		else:
			break
	print(cnt)


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	i_ = int(n / 2)
	i = i_
	c = s[i]
	while i < n and s[i] == c:
		i += 1
	r = (i - i_) * 2
	if n % 2 == 1:
		r -= 1
	print(r)


for i in range(int(input())):
	n = int(input())
	t = input()
	k = n // 2
	p = t[k]
	i = 0
	while k + i < n and t[k + i] == p:
		i += 1
	if n % 2 == 0:
		print(i * 2)
	else:
		print(i * 2 - 1)


t = int(input(''))
for z in range(t):
	n = int(input(''))
	s = input('')
	if len(set(s)) == 1:
		print(len(s))
	else:
		p = n // 2
		q = s[p]
		c = 0
		for i in range(p, n):
			if s[i] == q:
				c += 1
			else:
				break
		for j in range(p - 1, 0, -1):
			if s[j] == q:
				c += 1
			else:
				break
		print(c)


tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input()
	c = 0
	for i in range((n - 1) // 2, -1, -1):
		if s[i] == s[(n - 1) // 2]:
			c += 1
		else:
			break
	print(2 * c - (n & 1))


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	if n == 2:
		print(2)
	elif n == 3 and s.count(s[0]) == 3:
		print(3)
	elif n == 3:
		print(1)
	else:
		x = s[0:n // 2]
		for i in range(len(x) - 1, 0, -1):
			if x[i] == x[i - 1]:
				ans = ans + 1
			else:
				break
		ans = ans + 1
		if n % 2 == 0:
			print(ans * 2)
		elif x[len(x) - 1] == s[n // 2]:
			print(ans * 2 + 1)
		else:
			print(1)


t = int(input())
for _ in range(t):
	size = int(input())
	s = input()
	core = 0
	middle = int(size / 2)
	letter = s[middle]
	for i in range(middle + 1, size):
		if s[i] != letter:
			break
		core += 1
	if size % 2 == 0:
		core = 2 * core + 2
	else:
		core = core * 2 + 1
	print(core)


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


t = int(input())
for i in range(t):
	n = int(input())
	p = input()
	m = p[n // 2]
	counter = 0
	for j in range(n // 2, n):
		if p[j] == m:
			counter += 1
		else:
			break
	counter *= 2
	if n % 2 != 0:
		counter -= 1
	print(counter)


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 = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	if n % 2 == 1:
		ans = 1
	else:
		ans = 2
	for i in range(n // 2 + 1, n, 1):
		if string[i] == string[i - 1]:
			ans += 2
		else:
			break
	print(ans)


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


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


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


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	result = 0
	mc = s[n // 2]
	for x in s[n // 2:]:
		if x == mc:
			result += 1
		else:
			break
	print(result * 2 - (1 if n % 2 != 0 else 0))


T = int(input())
for _ in range(T):
	N = int(input())
	S = input().strip()
	if N % 2 == 1:
		center = N // 2
		ans = 1
		for i in range(center + 1, N):
			if S[center] == S[i]:
				ans += 2
			else:
				break
	else:
		center = N // 2
		ans = 2
		for i in range(center + 1, N):
			if S[center] == S[i]:
				ans += 2
			else:
				break
	print(ans)


t = int(input())
for e in range(t):
	n = int(input())
	a = input()
	b = a[(n - 1) // 2]
	c = n % 2
	a = a[(n + 1) // 2:]
	for i in range(n // 2):
		if a[i] == b:
			c += 2
		else:
			break
	print(c)


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


t = int(input())
for t in range(t):
	n = int(input())
	s = input()
	k = n // 2
	while k < n and s[k] == s[n // 2]:
		k += 1
	if n % 2 == 0:
		print(2 * (k - n // 2))
		continue
	print(2 * (k - n // 2 - 1) + 1)


T = int(input())
for t in range(T):
	length = int(input())
	palindrome = input()
	cnt = 0
	index = int(length / 2)
	char = palindrome[index]
	while index < length and char == palindrome[index]:
		cnt += 1
		index += 1
	if length % 2 == 0:
		cnt *= 2
	else:
		cnt = cnt * 2 - 1
	print(cnt)


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


t = int(input())
for g in range(t):
	n = int(input())
	st = input()
	ch = st[n // 2]
	i = n // 2
	while st[i] == ch and i >= 0:
		i -= 1
	if len(st) % 2 == 0:
		print((n // 2 - i - 1) * 2)
	else:
		print((n // 2 - 1 - i) * 2 + 1)


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	m = n // 2
	c = 0
	while True:
		if s[m - 1] == s[m] and m != 0:
			c += 2
			m -= 1
		else:
			break
	if c == 0 or n & 1:
		print(c + 1)
	else:
		print(c)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n % 2 == 0:
		mid = n // 2 - 1
		check = s[mid]
		cnt = 0
		while mid >= 0 and s[mid] == check:
			cnt += 1
			mid -= 1
		print(cnt * 2)
	else:
		mid = n // 2
		check = s[mid]
		cnt = 0
		while mid >= 0 and s[mid] == check:
			cnt += 1
			mid -= 1
		print((cnt - 1) * 2 + 1)


for i in range(int(input())):
	x = int(input())
	y = input()
	v = y[x // 2:]
	c = 0
	for i in range(len(v) - 1):
		if v[i + 1] == v[i]:
			c += 1
		else:
			break
	if x % 2 == 1:
		print(c * 2 + 1)
	else:
		print(c * 2 + 2)