A string is called *boring* if all the characters of the string are same.

You are given a string S of length N, consisting of lowercase english alphabets. Find the length of the longest *boring* substring of S which occurs more than once.

Note that if there is no *boring* substring which occurs more than once in S, the answer will be 0.

A substring is obtained by deleting some (possibly zero) elements from the beginning of the string and some (possibly zero) elements from the end of the string.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N, denoting the length of string S.
- The next contains string S.

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

For each test case, output on a new line, the length of the longest *boring* substring of S which occurs more than once.

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

$1 ≤ T ≤ 1000$
$1 < N ≤ 2\cdot 10^{5}$
- The sum of $N$ over all test cases won't exceed $5\cdot 10^{5}$.
$S$ consists of lowercase english alphabets.

----- Sample Input 1 ------ 
4
3
aaa
3
abc
5
bcaca
6
caabaa

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

----- explanation 1 ------ 
Test case $1$: The length of the longest *boring* substring that occurs more than once is $2$. The *boring* substring of length $2$ occurring more than once is aa.

Test case $2$: There is no *boring* substring which occurs more than once. Thus, the answer is $0$.

Test case $3$: The length of the longest *boring* substring that occurs more than once is $1$. Some *boring* substrings of length $1$ occurring more than once are c and a.

Test case $4$: The length of the longest *boring* substring that occurs more than once is $2$. The *boring* substring of length $2$ occurring more than once is aa.

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	S = input()
	T = set(S)
	ans = 1
	if len(S) == len(T):
		ans = 0
	elif len(T) == 1:
		ans = N - 1
	else:
		d = {}
		s = 'A'
		for j in S:
			if s[-1] == j:
				if len(s) > ans:
					ans = len(s)
				s += j
			else:
				s = j
			if s[0] + str(len(s)) in d and len(s) > ans:
				ans = len(s)
			elif len(s) > 1:
				d[s[0] + str(len(s))] = 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	L1 = input()
	L = [[0, 0] for j in range(32)]
	j = 0
	while j < n:
		s = L1[j]
		length = 1
		i = j + 1
		while True:
			if i == n:
				break
			if L1[i] == s:
				length += 1
			if L1[i] != s:
				break
			i += 1
		j = i
		if length > L[ord(s) - 97][0]:
			L[ord(s) - 97][0] = length
			L[ord(s) - 97][1] = 1
		elif length == L[ord(s) - 97][0]:
			L[ord(s) - 97][1] += 1
	L3 = [0]
	for j in range(32):
		[a, b] = L[j]
		if b > 1:
			L3.append(a)
		elif b == 1:
			L3.append(a - 1)
	print(max(L3))


t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	Max = 0
	d = {}
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = [1, 1]
			k = 1
		elif prev == s[i]:
			k += 1
			if k > d[prev][0]:
				d[prev][0] = k
				d[prev][1] = 1
			elif k == d[prev][0]:
				d[prev][1] += 1
		else:
			if d[s[i]][0] == 1:
				d[s[i]][1] += 1
			k = 1
		prev = s[i]
	Max = []
	for i in d:
		if d[i] > Max:
			Max = d[i]
	if Max[1] == 1:
		print(Max[0] - 1)
	else:
		print(Max[0])


from functools import reduce

def find_ind(a, j):
	x = []
	for i in range(len(a)):
		if a[i] == j:
			x.append(i)
	return x
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	acount = []
	alett = []
	i = 1
	if s[0] != s[1]:
		acount.append(1)
		alett.append(s[0])
	while i < n:
		count = 1
		j = i
		lett_store = s[i]
		while i < n and s[i] == s[i - 1]:
			count += 1
			i += 1
		if j == i:
			i += 1
		acount.append(count)
		alett.append(lett_store)
	m = reduce(max, acount)
	arr = find_ind(acount, m)
	store = []
	for i in arr:
		store.append(alett[i])
	if len(store) == 1:
		print(m - 1)
		continue
	flag = True
	for i in range(len(store) - 1):
		for j in range(i + 1, len(store)):
			if store[i] == store[j]:
				print(m)
				flag = False
				break
		if not flag:
			break
	if flag:
		print(m - 1)


for i in range(int(input())):
	n = int(input())
	s = [*input()]
	c = set(s)
	d = {}
	for e in c:
		d[e] = []
	curr = 0
	last = s[0]
	for j in range(n - 1):
		if s[j] != s[j + 1]:
			d[last].append(j + 1 - curr)
			curr = j + 1
			last = s[j + 1]
	d[last].append(n - curr)
	ans = 0
	for elem in d.values():
		ma = max(elem)
		if ma < ans:
			continue
		if elem.count(ma) == 1:
			ans = max(ans, ma - 1)
		else:
			ans = max(ans, ma)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	mx = [[0, 0] for _ in range(26)]
	(curch, curlen) = (s[0], 0)
	for i in range(n):
		if s[i] == curch:
			curlen += 1
		if i == n - 1 or s[i] != s[i + 1]:
			pos = ord(curch) - ord('a')
			if curlen > mx[pos][0]:
				mx[pos] = [curlen, 0]
			if curlen == mx[pos][0]:
				mx[pos][1] += 1
			if i < n - 1:
				(curch, curlen) = (s[i + 1], 0)
	ans = 0
	for i in range(26):
		if mx[i][1] > 1:
			ans = max(ans, mx[i][0])
		else:
			ans = max(ans, mx[i][0] - 1)
	print(ans)


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	string = input()
	string = string + 'X'
	hashmap = {}
	left = 0
	right = 1
	while right <= length:
		if string[left] == string[right]:
			right += 1
		else:
			hashmap[string[left:right]] = 1 + hashmap.get(string[left:right], 0)
			left = right
			right += 1
	if max(hashmap.values()) == 1:
		ans = 0
		boring = 0
		for strings in hashmap:
			boring = max(boring, len(strings))
		ans = boring - 1
	else:
		ans = 0
		boring = 0
		boring2 = 0
		for strings in hashmap:
			boring = max(boring, len(strings))
			if hashmap[strings] > 1:
				boring2 = max(boring2, len(strings))
		ans = max(boring - 1, boring2)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(input())
	a = []
	a.append(l[0])
	k = 0
	for j in range(1, n):
		if l[j] == a[k][0]:
			a[k] = a[k] + l[j]
		else:
			k = k + 1
			a.append(l[j])
	b = {}
	for j in a:
		b[j] = 0
	for j in a:
		b[j] = b[j] + 1
	mx = 0
	for j in b:
		if b[j] == 1:
			if mx < len(j) - 1:
				mx = len(j) - 1
		elif len(j) > mx:
			mx = len(j)
	print(mx)


def ans(s):
	i = 0
	hm = {}
	current = ''
	while i < len(s):
		if len(current) == 0:
			current += s[i]
		elif current[-1] == s[i]:
			current += s[i]
		else:
			if current in hm.keys():
				hm[current] += 1
			else:
				hm[current] = 1
			current = s[i]
		i += 1
	if current in hm.keys():
		hm[current] += 1
	else:
		hm[current] = 1
	arr = []
	for y in hm.keys():
		arr.append([len(y), hm[y]])
	m1 = 0
	for y in arr:
		if y[0] > m1:
			if y[1] == 1:
				m1 = y[0] - 1
			else:
				m1 = y[0]
	return m1
test_cases = int(input())
while test_cases != 0:
	d_ = input()
	d = input()
	print(ans(d))
	test_cases -= 1


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
lower = [chr(x) for x in range(ord('a'), ord('z') + 1)]
ans = []

def find_two_max(A):
	(mx1, mx2) = (A[0], A[1]) if A[0] > A[1] else (A[1], A[0])
	for a in A[2:]:
		if a > mx1:
			(mx1, mx2) = (a, mx1)
		elif a > mx2:
			mx2 = a
	return (mx1, mx2)
for _ in range(inp()):
	N = inp()
	S = insr()
	if N == 1:
		ans.append(0)
		continue
	dic = {x: [] for x in lower}
	(c, old) = (1, S[0])
	for s in S[1:]:
		if old == s:
			c += 1
		else:
			dic[old].append(c)
			c = 1
			old = s
	else:
		dic[s].append(c)
	an = 0
	for ch in dic:
		s = dic[ch]
		if s:
			if len(s) == 1:
				an = max(an, s[0] - 1)
			else:
				(mx1, mx2) = find_two_max(s)
				an = max(an, max(mx1 - 1, mx2))
	ans.append(an)
outplt(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	e = []
	c = 0
	d = 0
	for y in range(1, n):
		if s[y] != s[y - 1]:
			if len(e) == 0:
				e.append(s[y - 1])
				c = y
				d = y
				continue
			if len(e) > 0:
				if d == y - c:
					e.append(s[y - 1])
					c = y
					continue
				if d < y - c:
					e = []
					e.append(s[y - 1])
					d = y - c
			c = y
	if len(e) > 0:
		if d == n - c:
			e.append(s[n - 1])
		if d < n - c:
			print(n - c - 1)
			continue
	else:
		print(n - 1)
		continue
	if len(set(e)) == len(e):
		print(d - 1)
	else:
		print(d)


def all_unique(item):
	return len(set(item)) == len(item)
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	e = []
	c = 0
	d = 0
	for y in range(1, n):
		if s[y] != s[y - 1]:
			if len(a) == 0:
				a.append(y)
				e.append(s[y - 1])
				c = y
				d = y
				continue
			if len(a) > 0:
				if d == y - c:
					a.append(y)
					e.append(s[y - 1])
					c = y
					continue
				if d < y - c:
					a = []
					e = []
					a.append(y)
					e.append(s[y - 1])
					d = y - c
			c = y
	if len(a) > 0:
		if d == n - c:
			a.append(n)
			e.append(s[n - 1])
		if d < n - c:
			print(n - c - 1)
			continue
	else:
		print(n - 1)
		continue
	if all_unique(e):
		print(d - 1)
	else:
		print(d)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	c = 0
	d = 0
	for y in range(1, n):
		if s[y] != s[y - 1]:
			if len(a) == 0:
				a.append([y, s[y - 1]])
				c = y
				d = y
				continue
			if len(a) > 0:
				if d == y - c:
					a.append([y, s[y - 1]])
					c = y
					continue
				if d < y - c:
					a = []
					a.append([y, s[y - 1]])
					d = y - c
			c = y
	if len(a) > 0:
		if d == n - c:
			a.append([n, s[n - 1]])
		if d < n - c:
			print(n - c - 1)
			continue
	else:
		print(n - 1)
		continue
	b = len(a)
	for x in range(b):
		for y in range(x + 1, b):
			if a[x][1] == a[y][1]:
				print(d)
				c = 0
				break
		if c == 0:
			break
	if c != 0:
		print(d - 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	c = 0
	for y in range(1, n):
		if s[y] != s[y - 1]:
			if len(a) == 0:
				a.append([y, y])
				c = y
				continue
			if len(a) > 0:
				if a[-1][1] == y - c:
					a.append([y, y - c])
				if a[-1][1] < y - c:
					a.clear()
					a.append([y, y - c])
			c = y
		if y == n - 1:
			if len(a) > 0:
				if a[-1][1] == n - c:
					a.append([n, n - c])
				if a[-1][1] < n - c:
					a.clear()
					a.append([n, n - c])
			else:
				a.append([n, n - c])
	b = len(a)
	if b < 2:
		print(a[0][1] - 1)
		continue
	for x in range(b):
		for z in range(x + 1, b):
			if s[a[x][0] - 1] == s[a[z][0] - 1]:
				print(a[x][1])
				c = 'a'
				break
		if c == 'a':
			break
	if c != 'a':
		print(a[0][1] - 1)
		continue


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	S = insr()
	an = 0
	if N == 1:
		ans.append(0)
		continue
	dic = {chr(x): [] for x in range(ord('a'), ord('z') + 1)}
	c = 1
	for i in range(1, N):
		if S[i - 1] == S[i]:
			c += 1
		else:
			dic[S[i - 1]].append(c)
			c = 1
	else:
		dic[S[-1]].append(c)
	an = 0
	for ch in dic:
		s = sorted(dic[ch], reverse=True)
		if s:
			if len(s) == 1:
				an = max(an, s[0] - 1)
			else:
				an = max(an, max(s[0] - 1, s[1]))
	ans.append(an)
outplt(ans)


def compres(n):
	z = []
	max_val = 0
	c = 1
	t = n[0]
	for i in range(1, len(n)):
		if t == n[i]:
			c += 1
		else:
			if c > max_val:
				z = [t]
				max_val = c
			elif c == max_val:
				z.append(t)
			c = 1
			t = n[i]
	if c > max_val:
		z = [t]
		max_val = c
	elif c == max_val:
		z.append(t)
	return (z, max_val)
for _ in range(int(input())):
	n = int(input())
	a = input()
	(z, max_val) = compres(a)
	flag = 1
	for i in z:
		if a.count(i * max_val) > 1:
			flag = 0
			break
	print(max_val - flag)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	temp = s[0]
	for i in range(1, n):
		if s[i] != s[i - 1]:
			a.append(temp)
			temp = ''
		temp += s[i]
	if len(temp):
		a.append(temp)
	a.sort()
	ans = 0
	for i in range(len(a)):
		ans = max(ans, len(a[i]) - 1)
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			ans = max(ans, len(a[i]))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	subs = {}
	for i in range(97, 123):
		subs[chr(i)] = []
	curchr = s[0]
	sublen = 1
	for j in range(1, n):
		if s[j] == curchr:
			sublen += 1
		else:
			subs[curchr].append(sublen)
			curchr = s[j]
			sublen = 1
	subs[curchr].append(sublen)
	strings = []
	for ch in subs:
		if len(subs[ch]) > 0:
			if len(subs[ch]) == 1:
				strings.append(subs[ch][0] - 1)
			elif subs[ch].count(max(subs[ch])) > 1:
				strings.append(max(subs[ch]))
			else:
				strings.append(max(subs[ch]) - 1)
	print(max(strings))


for i in range(int(input())):
	n = int(input())
	s = input()
	l1 = []
	l2 = []
	last_char = s[0]
	m = 0
	for i in s:
		if last_char != i:
			l1.append(last_char)
			l2.append(m)
			last_char = i
			m = 1
		else:
			m += 1
	l1.append(last_char)
	l2.append(m)
	flag = False
	lexi = 'abcdefghijklmnopqrstuvwxyz'
	if n < 27 and max(l2) < 2:
		for i in lexi:
			if s.count(i) > 1:
				flag = True
				break
	else:
		flag = True
	if flag:
		maxy = max(l2) - 1
		d = {}
		for i in range(26):
			d[lexi[i]] = [0, 0]
		for i in range(len(l1)):
			if d[l1[i]][1] == 0:
				d[l1[i]][1] = l2[i]
			elif d[l1[i]][0] == 0:
				d[l1[i]][0] = min(l2[i], d[l1[i]][1])
				d[l1[i]][1] = max(l2[i], d[l1[i]][1])
			elif l2[i] > d[l1[i]][1]:
				d[l1[i]][0] = d[l1[i]][1]
				d[l1[i]][1] = l2[i]
			elif l2[i] > d[l1[i]][0]:
				d[l1[i]][0] = l2[i]
		for i in lexi:
			if d[i][0] == 0:
				continue
			else:
				maxy = max(maxy, d[i][0])
		print(maxy)
	else:
		print(0)


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	bore = s[0]
	b_strs = []
	for i in range(1, n):
		if i == n - 1:
			if s[i] == s[i - 1]:
				bore += s[i]
			else:
				b_strs.append(bore)
				bore = s[i]
			b_strs.append(bore)
		elif s[i] == s[i - 1]:
			bore += s[i]
		else:
			if len(bore) >= 1:
				b_strs.append(bore)
			bore = s[i]
	hashh = [0] * 26
	times = [0] * 26
	for el in b_strs:
		ind = ord(el[0]) % 97
		len_ = len(el)
		if len_ == hashh[ind]:
			times[ind] = 2
		else:
			if len_ > hashh[ind]:
				times[ind] = 1
			hashh[ind] = max(len_, hashh[ind])
	ans = 0
	for i in range(26):
		if hashh[i] > ans:
			if times[i] == 2:
				ans = hashh[i]
			elif times[i] == 1 and hashh[i] == 1:
				ans = 0
			else:
				ans = hashh[i] - 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	x = input()
	y = dict()
	for i in range(n):
		ch = x[i]
		if i == 0:
			y[ch] = []
			curr_char = ch
			curr_index = 0
		if ch != curr_char:
			char = x[i - 1]
			length = i - curr_index
			if char in y:
				y[char].append(length)
			else:
				y[char] = [length]
			curr_char = x[i]
			curr_index = i
		if i == n - 1:
			char = x[i]
			length = i - curr_index + 1
			if char in y:
				y[char].append(length)
			else:
				y[char] = [length]
	max_score = -1
	for letter in y:
		letter_list = y[letter]
		winner = max(letter_list)
		letter_list.remove(winner)
		if letter_list:
			runner = max(letter_list)
			score = winner if winner == runner else winner - 1
		else:
			score = winner - 1
		if score > max_score:
			max_score = score
	print(max_score)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input() + '?'
	c = Counter()
	char = s[0]
	length = 1
	for j in range(1, n + 1):
		if s[j] == char:
			length += 1
		else:
			c[char * length] += 1
			char = s[j]
			length = 1
	maxlength = 0
	for (wo, count) in c.items():
		if count > 1:
			maxlength = max(maxlength, len(wo))
		else:
			maxlength = max(maxlength, len(wo) - 1)
	print(maxlength)


def process_ans(letters, N):
	flag = 0
	ans = []
	for letr in letters:
		if len(letters[letr]) > 1:
			flag = 1
			mx = max(letters[letr])
			cnt = letters[letr].count(mx)
			if cnt > 1 or mx == 1:
				ans.append(mx)
			else:
				ans.append(mx - 1)
		elif letters[letr][0] > 1:
			ans.append(letters[letr][0] - 1)
		else:
			ans.append(0)
	return max(ans)
T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	letters = {}
	length = 1
	Ans = 0
	if N == 1:
		Ans = 0
	else:
		for i in range(1, N):
			if S[i] == S[i - 1]:
				length = length + 1
			else:
				if S[i - 1] in letters:
					letters[S[i - 1]].append(length)
				else:
					letters[S[i - 1]] = [length]
				length = 1
			if i == N - 1:
				if S[i] in letters:
					letters[S[i]].append(length)
				else:
					letters[S[i]] = [length]
		Ans = process_ans(letters, N)
	print(Ans)


T = int(input())
for t in range(T):
	input()
	d = {c: [0, 0] for c in 'abcdefghijklmnopqrstuvwxyz'}
	cur = ''
	inp = input()
	for c in inp:
		if len(cur) > 0 and cur[0] == c:
			cur += c
		else:
			cur = c
		ln = len(cur)
		d[c][1] = max(d[c][1], ln if d[c][0] >= ln else ln - 1)
		d[c][0] = max(d[c][0], ln)
	print(max((boring_numbers[1] for boring_numbers in d.values())))


T = int(input())
for t in range(T):
	N = int(input())
	d = {c: [0, 0] for c in 'abcdefghijklmnopqrstuvwxyz'}
	cur = []
	inp = input()
	for c in inp:
		if len(cur) > 0 and cur[0] == c:
			cur += c
		else:
			cur = c
		l = len(cur)
		if d[c][0] >= l:
			d[c][1] = max(d[c][1], l)
		else:
			d[c][1] = max(d[c][1], l - 1)
		d[c][0] = max(d[c][0], len(cur))
	bor_max = 0
	for (c, ns) in d.items():
		bor_max = max(ns[1], bor_max)
	print(bor_max)


from collections import Counter, deque, defaultdict
import statistics
import math

def notSquare(n):
	x = int(math.sqrt(n))
	if x * x == n:
		return False
	return True

def solve(n, s):
	hash = [[] for _ in range(26)]
	beg = 0
	end = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			end = i
		else:
			ch = ord(s[i - 1]) - ord('a')
			hash[ch].append(end - beg + 1)
			beg = i
			end = i
	hash[ord(s[-1]) - ord('a')].append(end - beg + 1)
	arr = []
	for i in range(26):
		try:
			arr.append(max(hash[i]))
		except ValueError:
			arr.append(0)
	multiples = []
	for i in range(26):
		try:
			hash[i].sort(reverse=True)
			val = hash[i][1]
			val1 = hash[i][0]
			if val == val1:
				multiples.append(True)
			else:
				multiples.append(False)
		except IndexError:
			multiples.append(False)
	maxi = -1
	for i in range(26):
		if arr[i] >= maxi:
			if multiples[i]:
				maxi = max(maxi, arr[i])
			else:
				maxi = max(maxi, arr[i] - 1)
	return maxi
for test in range(int(input())):
	n = int(input())
	s = input().strip()
	print(solve(n, s))


for _ in range(int(input())):
	n = int(input())
	a = input()
	s = dict()
	f = dict()
	for i in range(26):
		s[chr(i + 97)] = 0
		f[chr(i + 97)] = 0
	s['#'] = f['#'] = 0
	pa = '#'
	pc = 0
	for c in a:
		if c == pa:
			pc += 1
		else:
			if s[pa] < pc:
				s[pa] = pc
				f[pa] = 1
			elif s[pa] == pc:
				f[pa] += 1
			pa = c
			pc = 1
	if s[pa] < pc:
		s[pa] = pc
		f[pa] = 1
	elif s[pa] == pc:
		f[pa] += 1
	a = []
	for i in s:
		if s[i] == 0:
			continue
		a.append((s[i], f[i], i))
	a.sort(reverse=True)
	(c, f, a) = a[0]
	if f < 2:
		print(c - 1)
	else:
		print(c)


from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	S = input() + '?'
	C = Counter()
	char = S[0]
	length = 1
	for i in range(1, N + 1):
		if S[i] == char:
			length += 1
		else:
			C[char * length] += 1
			char = S[i]
			length = 1
	maxLen = 0
	for (sub, count) in C.items():
		if count > 1:
			maxLen = max(maxLen, len(sub))
		else:
			maxLen = max(maxLen, len(sub) - 1)
	print(maxLen)


from heapq import heappop, heappush, heapify
for i in range(int(input())):
	input()
	s = input()
	v = {}
	for j in range(len(s)):
		if s[j] not in v:
			v[s[j]] = []
			heapify(v[s[j]])
	count = 1
	for j in range(len(s) - 1):
		if s[j] == s[j + 1]:
			count += 1
		else:
			heappush(v[s[j]], -1 * count)
			count = 1
	heappush(v[s[-1]], -1 * count)
	ma = -238127938718
	y = -20
	for j in v.keys():
		x = -1 * heappop(v[j])
		if len(v[j]) != 0:
			y = -1 * heappop(v[j])
		if y == -20:
			ma = max(ma, x - 1)
		elif x == y:
			ma = max(ma, x)
		else:
			ma = max(ma, x - 1)
	print(ma)


for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = [1 for i in range(n)]
	d = {}
	for i in range(1, n):
		if s[i] == s[i - 1]:
			arr[i] = arr[i - 1] + 1
	mx = max(arr)
	my = 0
	for i in range(n):
		if s[i] in d:
			if d[s[i]] < arr[i]:
				d[s[i]] = arr[i]
			elif d[s[i]] == arr[i]:
				my = max(my, arr[i])
		else:
			d[s[i]] = arr[i]
	print(max(mx - 1, my))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(i, j) = (0, 1)
	d = {}
	while i < n and j <= n:
		while j < n and s[j - 1] == s[j]:
			j += 1
		if s[i] in d:
			d[s[i]] += [j - i]
		else:
			d[s[i]] = [j - i]
		i = j
		j += 1
	ans = 0
	for (i, j) in d.items():
		l = j.copy()
		l.sort()
		if len(l) > 1:
			if l[len(l) - 1] == l[len(l) - 2]:
				ans = max(l[len(l) - 1], ans)
			else:
				ans = max(l[len(l) - 1] - 1, ans)
		else:
			ans = max(l[0] - 1, ans)
	print(ans)


for _ in range(int(input())):
	n = input()
	s = input()
	(d, prev, count, t, maxLen) = ({}, s[0], 1, s[0], 0)
	s = s[1:]
	for i in s:
		if i == prev:
			t += i
		else:
			d[t] = d.get(t, 0) + 1
			t = i
		prev = i
	if len(s):
		d[t] = d.get(t, 0) + 1
	for i in d:
		if len(i) > maxLen:
			if d[i] > 1:
				maxLen = max(maxLen, len(i))
			else:
				maxLen = max(maxLen, len(i) - 1)
	print(maxLen)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	prevL = [s[0], 0]
	result = 0
	for j in range(1, n):
		if s[j] == prevL[0]:
			if j == n - 1 and j - prevL[1] > result:
				result = j - prevL[1]
			else:
				continue
		else:
			if j - prevL[1] > result and s[prevL[1]:j] in s[j + 1:]:
				result = j - prevL[1]
			elif j - prevL[1] - 1 > result:
				result = j - prevL[1] - 1
			prevL[0] = s[j]
			prevL[1] = j
	print(result)


for _ in range(int(input())):
	n = int(input())
	s = input()
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ans = 0
	for k in range(len(alpha)):
		maxlen = 0
		i = 0
		while i < n:
			if s[i] != alpha[k]:
				i += 1
				continue
			j = i
			while i + 1 < n and s[i] == s[i + 1]:
				i += 1
			l = i - j + 1
			if maxlen < l:
				maxlen = l
			elif maxlen == l:
				ans = max(ans, l)
			i += 1
		ans = max(ans, maxlen - 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	i = 0
	while i < n:
		subs = s[i]
		j = i
		while i + 1 < n and s[i] == s[i + 1]:
			subs += s[i + 1]
			i += 1
		l = i - j + 1
		if subs in s[i + 1:]:
			ans = max(ans, l)
		else:
			ans = max(ans, l - 1)
		i += 1
	print(ans)


from collections import *
from math import *
from sys import *
T = int(input())
for _ in range(T):
	N = int(input())
	B = input()
	prev = ''
	cnt = 0
	A = {}
	ans = 0
	for i in B:
		curr = i
		if curr == prev:
			cnt += 1
		else:
			cnt = 1
			prev = curr
		if curr not in A:
			A[curr] = cnt
		elif A[curr] >= cnt:
			ans = max(ans, cnt)
		else:
			A[curr] = cnt
	print(max(ans, max(A.values()) - 1))


case = int(input())
for i in range(case):
	n = int(input())
	s = input()
	prev = ''
	count = 0
	res = 0
	char = {}
	for j in range(n):
		curr = s[j]
		if curr == prev:
			count += 1
		else:
			count = 1
			prev = curr
		if curr not in char:
			char[curr] = count
		elif char[curr] >= count:
			res = max(res, count)
		else:
			char[curr] = count
	for key in char:
		res = max(res, char[key] - 1)
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	c = 0
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			c += 1
		else:
			c = 0
		ans = max(c, ans)
	d = {}
	c = 1
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			c += 1
		else:
			if s[i] not in d:
				d[s[i]] = c
			else:
				ans = max(ans, min(c, d[s[i]]))
				if d[s[i]] < c:
					d[s[i]] = c
			c = 1
	if s[len(s) - 1] in d:
		ans = max(ans, min(d[s[len(s) - 1]], c))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = input()
	ans = 0
	for i in range(97, 122):
		x = chr(i)
		c = 0
		m = 0
		for j in a:
			if x == j:
				c += 1
			else:
				if m == c:
					ans = max(ans, m)
				elif c > m:
					m = c
					ans = max(ans, m - 1)
				c = 0
		else:
			if m == c:
				ans = max(ans, m)
			elif c > m:
				m = c
				ans = max(ans, m - 1)
	print(ans)


from collections import defaultdict
import math
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	sub = s[0]
	d = defaultdict(int)
	ans = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			sub += s[i]
		else:
			d[sub] += 1
			sub = s[i]
	d[sub] += 1
	l = [k for [k, v] in d.items() if v > 1 or len(k) > 1]
	l.sort(key=lambda x: len(x), reverse=True)
	val = 0
	for x in l:
		if d[x] == 1:
			val = len(x) - 1
		else:
			val = len(x)
		ans = max(ans, val)
	print(ans)


for i in range(int(input())):
	num = int(input())
	str1 = input()
	str1 += '.'
	lis = []
	(s, t) = (1, 0)
	while s < len(str1):
		if str1[s - 1] == str1[s]:
			s += 1
		else:
			lis.append(str1[t:s])
			t = s
			s += 1
	dic = dict()
	mx = 0
	for j in lis:
		length = len(j)
		mx = max(mx, length)
		try:
			dic[length].append(j)
		except:
			dic[length] = list()
			dic[length].append(j)
	ans = list(set(dic[mx]))
	total = 0
	for i in ans:
		count = lis.count(i)
		total = max(count, total)
	if mx == 1 and total == 1:
		print(0)
	elif total == 1:
		print(mx - 1)
	else:
		print(mx)


from string import ascii_lowercase as a_to_z
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	ans = curLen = 1
	for i in range(1, N):
		if S[i] == S[i - 1]:
			curLen += 1
		if S[i] != S[i - 1] or i == N - 1:
			if curLen > ans:
				ans = curLen
			curLen = 1
	for ch in a_to_z:
		if S.count(ch * ans) > 1:
			print(ans)
			break
	else:
		print(ans - 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	my_dict = {}
	borlen = 1
	ans = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			borlen += 1
		else:
			if str(s[i - 1] + str(borlen)) not in my_dict:
				my_dict[str(s[i - 1] + str(borlen))] = 1
			else:
				my_dict[str(s[i - 1] + str(borlen))] += 1
			borlen = 1
	if str(s[n - 1] + str(borlen)) not in my_dict:
		my_dict[str(s[n - 1] + str(borlen))] = 1
	else:
		my_dict[str(s[n - 1] + str(borlen))] += 1
	freq_1 = [i for i in my_dict if my_dict[i] == 1]
	freq_g = [i for i in my_dict if my_dict[i] > 1]
	max_bor_g = 0
	max_bor_1 = 0
	for i in freq_g:
		if int(i[1:len(i)]) >= max_bor_g:
			max_bor_g = int(i[1:len(i)])
	for i in freq_1:
		if int(i[1:n]) >= max_bor_1:
			max_bor_1 = int(i[1:len(i)])
	if max_bor_g >= max_bor_1 - 1:
		print(max_bor_g)
	else:
		print(max_bor_1 - 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	hashmap = {}
	sub = ''
	for i in range(n):
		if i == n - 1:
			sub += s[i]
			if sub in hashmap:
				hashmap[sub] += 1
			else:
				hashmap[sub] = 1
		elif s[i] == s[i + 1]:
			sub += s[i]
		else:
			sub += s[i]
			if sub in hashmap:
				hashmap[sub] += 1
			else:
				hashmap[sub] = 1
			sub = ''
	res = 0
	for string in hashmap.keys():
		if hashmap[string] > 1:
			res = max(res, len(string))
		else:
			res = max(res, len(string) - 1)
	print(res)


def solution(l, n):
	l += '-'
	dic = dict()
	last = '_'
	app = ''
	for i in range(n):
		if last != l[i]:
			app = l[i]
		else:
			app += l[i]
		if l[i] != l[i + 1]:
			if app not in dic:
				dic[app] = 1
			else:
				dic[app] += 1
			if len(app) > 1:
				substr = app[:-1]
				if substr not in dic:
					dic[substr] = 2
				else:
					dic[substr] += 2
		last = l[i]
	ans = 0
	for key in dic:
		if dic[key] > 1:
			ans = max(ans, len(key))
	print(ans)
for _ in range(int(input())):
	n = int(input())
	l = input()
	solution(l, n)


n = int(input())
for x in range(n):
	l = int(input())
	li = list(' ' + input())
	li2 = set(li)
	mfre = 0
	fre = 0
	for i in li2:
		mi = 0
		ma = 0
		x = 0
		fre = 0
		for j in range(l + 1):
			if li[j] == i and li[j - 1] != i:
				x = 1
				if mi == 1 and ma == 0:
					ma = 1
				elif mi == 0:
					mi = 1
			elif li[j] == li[j - 1] == i:
				x = x + 1
			elif x != 0 and x != 1:
				if x >= ma:
					if ma != 0:
						mi = ma
					ma = x
					x = 0
		if x >= ma and x != 1:
			if ma != 0:
				mi = ma
			ma = x
		if mi != 0 and ma != 0:
			if ma == mi:
				fre = ma
			else:
				fre = ma - 1
		if fre > mfre:
			mfre = fre
	print(mfre)


for _ in range(int(input())):
	N = int(input())
	S = input()
	count = {}
	temp = ''
	for i in range(N):
		if i == N - 1:
			temp += S[i]
			if temp in count:
				count[temp] += 1
			else:
				count[temp] = 1
		elif S[i] == S[i + 1]:
			temp += S[i]
		else:
			temp += S[i]
			if temp in count:
				count[temp] += 1
			else:
				count[temp] = 1
			temp = ''
	output = 0
	for i in count:
		if count[i] > 1:
			output = max(output, len(i))
		else:
			output = max(output, len(i) - 1)
	print(output)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	d = {}
	a = ''
	for i in range(n):
		if i >= n - 1:
			a += s[i]
			if a not in d:
				d[a] = 0
			d[a] += 1
			a = ''
		elif s[i] == s[i + 1]:
			a += s[i]
		else:
			a += s[i]
			if a not in d:
				d[a] = 0
			d[a] += 1
			a = ''
	l = []
	for (i, j) in d.items():
		if j == 1:
			l.append(len(i) - 1)
		else:
			l.append(len(i))
	print(max(l))


time = int(input())
for _ in range(time):
	num = int(input())
	string = input()
	d = {}
	a = ''
	for i in range(0, num):
		if i >= num - 1:
			a += string[i]
			if a not in d:
				d[a] = 0
			d[a] += 1
			a = ''
		elif string[i] == string[i + 1]:
			a += string[i]
		else:
			a += string[i]
			if a not in d:
				d[a] = 0
			d[a] += 1
			a = ''
	l = []
	for (i, j) in d.items():
		if j == 1:
			l.append(len(i) - 1)
		else:
			l.append(len(i))
	print(max(l))


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	s = s + ' '
	(i, ma) = (0, 0)
	while i < n:
		sub = s[i]
		while s[i] == s[i + 1]:
			sub = sub + s[i]
			i = i + 1
		m = s[i + 1:]
		if sub in m:
			ma = max(ma, len(sub))
		else:
			ma = max(ma, len(sub) - 1)
		i = i + 1
	print(ma)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	substrs = []
	ss = [s[0]]
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ss.append(s[i + 1])
		else:
			substrs.append(''.join(ss))
			ss = [s[i + 1]]
	substrs.append(''.join(ss))
	d = {}
	for ss in substrs:
		d.setdefault(ss, 0)
		d[ss] += 1
	mx = 0
	for (k, v) in d.items():
		l = len(k)
		if v > 1 and l > mx:
			mx = l
		elif v == 1 and l - 1 > mx:
			mx = l - 1
	print(mx)


import re
for tc in range(int(input())):
	n = int(input())
	s = input()
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	maxlongest = 0
	for j in alpha:
		regex = j + '+'
		letters = re.findall(regex, s)
		maxlen = 0
		flagi = 0
		countmax = 0
		if len(letters) > 0:
			for i in range(len(letters)):
				if len(letters[i]) > maxlen:
					maxlen = len(letters[i])
					flagi = i
			countmax = letters.count(letters[flagi])
			if countmax > 1:
				longestboring = maxlen
			else:
				longestboring = maxlen - 1
			if longestboring > maxlongest:
				maxlongest = longestboring
	print(maxlongest)


t = int(input())
for _ in range(t):
	d = {}
	n = int(input())
	s = input()
	mx = 0
	i = 0
	while i < n:
		c = 1
		ss = s[i]
		while i < n - 1 and s[i] == s[i + 1]:
			c += 1
			i += 1
			ss += s[i]
		mx = max(mx, c - 1)
		d[ss] = d.get(ss, 0) + 1
		if d[ss] == 2:
			mx = max(mx, len(ss))
		i += 1
	print(mx)


from collections import Counter, defaultdict
import sys
import math

def sol(s, n):
	count = 0
	d = defaultdict(list)
	i = 0
	prev = None
	while i < n:
		if s[i] == prev:
			count += 1
		elif prev == None:
			count = 1
			prev = s[i]
		else:
			d[prev].append(count)
			count = 1
			prev = s[i]
		i += 1
	d[prev].append(count)
	for x in d:
		d[x].sort()
	ans = 0
	for i in d:
		if len(d[i]) == 1 and d[i][0] == 1:
			continue
		elif len(d[i]) == 1:
			ans = max(ans, d[i][0] - 1)
		else:
			ans = max(ans, d[i][-1] - 1, d[i][-2])
	return ans
input = sys.stdin.readline

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

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

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	s = insr()
	print(sol(s, n))


T = int(input())
for i in range(T):
	d = {}
	n = int(input())
	s = input()
	maxx = 0
	i = 0
	while i < n:
		count = 1
		sub = s[i]
		while i < n - 1 and s[i] == s[i + 1]:
			count += 1
			i += 1
			sub += s[i]
		maxx = max(maxx, count - 1)
		d[sub] = d.get(sub, 0) + 1
		if d[sub] > 1:
			maxx = max(maxx, len(sub))
		i += 1
	print(maxx)


for _ in range(int(input())):
	l = int(input())
	s = input()
	maxmap = {}
	maxe = 0
	for i in range(l):
		c = s[i]
		if not c in maxmap:
			maxmap[c] = [1]
		elif s[i - 1] == c:
			maxmap[c][-1] += 1
		else:
			maxmap[c].append(1)
	for (key, val) in maxmap.items():
		if len(val) == 1 and val[0] == 1:
			continue
		elif len(val) == 1 and val[0] - 1 > maxe:
			maxe = val[0] - 1
		elif max(val) > maxe:
			if val.count(max(val)) > 1:
				maxe = max(val)
			else:
				maxe = max(val) - 1
	print(maxe)


import collections
for t in range(int(input())):
	n = int(input())
	s = input()
	longest_col = collections.defaultdict(int)
	boring_list = collections.defaultdict(int)
	cur = s[0]
	for i in s[1:]:
		if i == cur[0]:
			cur += i
		else:
			if longest_col[cur[0]] > 0:
				boring_list[cur[0]] = max(boring_list[cur[0]], min(longest_col[cur[0]], len(cur)), len(cur) - 1)
			else:
				boring_list[cur[0]] = len(cur) - 1
			if len(cur) > longest_col[cur[0]]:
				longest_col[cur[0]] = len(cur)
			cur = i
	else:
		boring_list[cur[0]] = max(boring_list[cur[0]], min(longest_col[cur[0]], len(cur)), len(cur) - 1)
	max_n = 0
	for v in boring_list:
		if boring_list[v] > max_n:
			max_n = boring_list[v]
	print(max_n)


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	d = defaultdict(int)
	p = s[0]
	res = ''
	for i in s:
		if i == p:
			res += i
		else:
			d[res] += 1
			p = i
			res = i
	d[res] += 1
	m = 0
	for (k, v) in d.items():
		if v > 1:
			m = max(m, len(k))
		else:
			m = max(m, len(k) - 1)
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	freq = {}
	s += '-'
	last = '-'
	substr = ''
	for i in range(n):
		if last == s[i]:
			substr += s[i]
		else:
			substr = s[i]
		if s[i] != s[i + 1]:
			if substr in freq:
				freq[substr] += 1
			else:
				freq[substr] = 1
			if len(substr) > 1:
				moreStr = substr[0:-1]
				if moreStr in freq:
					freq[moreStr] += 2
				else:
					freq[moreStr] = 2
		last = s[i]
	ans = 0
	for substr in freq:
		count = freq[substr]
		if count > 1:
			ans = max(ans, len(substr))
	print(ans)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print(0)
	else:
		count = 1
		m = 1
		l = []
		ele = s[0]
		for i in range(1, n):
			if ele == s[i]:
				count += 1
			else:
				count = 1
				ele = s[i]
			if m < count:
				m = count
		count = 1
		for i in range(n):
			if s[i] == ele:
				count += 1
			else:
				count = 1
				ele = s[i]
			if count == m:
				l.append(s[i])
		if m == 1:
			d = Counter(s)
			if max(d.values()) > 1:
				print(1)
			else:
				print(0)
		else:
			for i in l:
				s1 = i * m
				val = s.count(s1)
				if val > 1:
					print(m)
					break
			else:
				print(m - 1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	f = [0] * 26
	c = 1
	res = 0
	for i in range(1, n + 1):
		if i < len(s) and s[i] == s[i - 1]:
			c += 1
		else:
			j = ord(s[i - 1]) - 97
			if f[j] != 0 and f[j] <= c:
				res = max(res, max(c - 1, f[j]))
				f[j] = c
			elif f[j] == 0:
				f[j] = c
				res = max(res, f[j] - 1)
			c = 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = input()
	s = s + ' '
	m = []
	c = 1
	M = 0
	for i in range(n):
		if s[i] != s[i + 1]:
			if c >= M:
				M = c
				m.append(s[i])
			c = 1
		else:
			c += 1
	for j in m:
		if s.count(M * j) > 1:
			print(M)
			break
	else:
		print(M - 1)


def spoc(a, b):
	if b > a:
		aa = b
		b = a
		a = aa
	if b == 0:
		if a == 0:
			return 0
		else:
			return a - 1
	elif a > b:
		return a - 1
	else:
		return b
tests = int(input())
for _ in range(tests):
	del1 = []
	del2 = []
	for i in range(26):
		del1.append(0)
		del2.append(0)
	n = int(input())
	s = input()
	c = chr(96)
	poc = 0
	for x in s:
		if x != c:
			if c != chr(96):
				i = ord(c) - 97
				if del1[i] < del2[i]:
					if del1[i] < poc:
						del1[i] = poc
				elif del2[i] < del1[i]:
					if del2[i] < poc:
						del2[i] = poc
				elif del1[i] < poc:
					del1[i] = poc
			c = x
			poc = 1
		else:
			poc += 1
	i = ord(c) - 97
	if del1[i] < del2[i]:
		if del1[i] < poc:
			del1[i] = poc
	elif del2[i] < del1[i]:
		if del2[i] < poc:
			del2[i] = poc
	elif del1[i] < poc:
		del1[i] = poc
	m = 0
	for i in range(26):
		pos = spoc(del1[i], del2[i])
		if pos > m:
			m = pos
	print(m)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print(0)
		continue
	count = 1
	ele = s[0]
	l = []
	m = 0
	for i in range(1, n):
		if ele == s[i]:
			count += 1
		else:
			count = 1
			ele = s[i]
		if m < count:
			m = count
	count = 1
	for i in range(1, n):
		if s[i] == ele:
			count += 1
		else:
			count = 1
			ele = s[i]
		if count == m:
			l.append(s[i])
	if m == 1:
		s = list(s)
		d = dict(Counter(s))
		if max(d.values()) > 1:
			print(1)
		else:
			print(0)
	else:
		done = False
		for i in l:
			s1 = i * m
			val = s.count(s1)
			if val > 1:
				done = True
				break
		if done:
			print(m)
		else:
			print(m - 1)


from collections import defaultdict, Counter
for _ in range(int(input())):
	n = int(input())
	s = input().strip() + '-'
	d = defaultdict(int)
	last = '-'
	sub = ''
	for i in range(n):
		if last == s[i]:
			sub += s[i]
		else:
			sub = s[i]
		if s[i] != s[i + 1]:
			d[sub] += 1
			if len(sub) > 1:
				d[sub[:-1]] += 2
		last = s[i]
	mlen = 0
	for key in d:
		count = d[key]
		leng = len(key)
		if count > 1:
			mlen = max(mlen, leng)
	print(mlen)