Let's denote the $f(x)$ function for a string $x$ as the number of distinct characters that the string contains. For example $f({abc}) = 3$, $f({bbbbb}) = 1$, and $f({babacaba}) = 3$.

Given a string $s$, split it into two non-empty strings $a$ and $b$ such that $f(a) + f(b)$ is the maximum possible. In other words, find the maximum possible value of $f(a) + f(b)$ such that $a + b = s$ (the concatenation of string $a$ and string $b$ is equal to string $s$).


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the string $s$.

The second line contains the string $s$, consisting of lowercase English letters.

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


-----Output-----

For each test case, output a single integer  — the maximum possible value of $f(a) + f(b)$ such that $a + b = s$.


-----Examples-----

Input
5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz
Output
2
7
2
10
3


-----Note-----

For the first test case, there is only one valid way to split ${aa}$ into two non-empty strings ${a}$ and ${a}$, and $f({a}) + f({a}) = 1 + 1 = 2$.

For the second test case, by splitting ${abcabcd}$ into ${abc}$ and ${abcd}$ we can get the answer of $f({abc}) + f({abcd}) = 3 + 4 = 7$ which is maximum possible.

For the third test case, it doesn't matter how we split the string, the answer will always be $2$.

Difficulty: EASY
Tags: String algorithms

Complete search

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
def foo(s):
	hm = {}
	for ele in s:
		if ele not in hm:
			hm[ele] = 1
		else:
			hm[ele] += 1
	hm_l = {}
	hm_r = {}
	maxCount = 0
	count = 0
	for (i, ele) in enumerate(s):
		if count >= maxCount:
			maxCount = count
		if ele not in hm_l:
			hm_l[ele] = 1
			hm[ele] -= 1
			if hm[ele] == 0:
				hm.pop(ele)
		else:
			hm_l[ele] += 1
			hm[ele] -= 1
			if hm[ele] == 0:
				hm.pop(ele)
		count = len(hm_l) + len(hm)
	print(maxCount)
n = int(input())
ls = []
for _ in range(n):
	x = int(input())
	ls.append(input())
for ele in ls:
	foo(ele)


def solve():
	n = int(input())
	s = input()
	pref = [0] * n
	d = set()
	for i in range(n):
		d.add(s[i])
		pref[i] = len(d)
	d = set()
	ans = 0
	for i in range(n - 1, 0, -1):
		d.add(s[i])
		ans = max(ans, len(d) + pref[i - 1])
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	s = input().strip()
	d = {}
	ans = -1
	for i in s:
		d[i] = d.get(i, 0) + 1
	d1 = {}
	for (k, i) in enumerate(s):
		d[i] -= 1
		d1[i] = d1.get(i, 0) + 1
		if d[i] == 0:
			del d[i]
		ans = max(ans, len(d1) + len(d))
	print(ans)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

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

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys

def answer():
	pass

def solution():
	n = int(input())
	s = input()
	d = dict()
	for i in s:
		d[i] = d.get(i, 0) + 1
	ans = len(d.items())
	tmp = ans
	t = dict()
	for i in s:
		t[i] = t.get(i, 0) + 1
		d[i] -= 1
		if t[i] == 1:
			tmp += 1
		if d[i] == 0:
			tmp -= 1
		if ans < tmp:
			ans = tmp
	print(ans)
t = int(input())
for _ in range(t):
	solution()


def solve():
	t = int(input())
	while t != 0:
		s = ''
		n = int(input())
		s = str(input())
		mx = 0
		d = {}
		d_rev = {}
		st = set()
		st.clear()
		for i in range(n):
			st.add(s[i])
			d[i] = len(st)
		st.clear()
		for i in reversed(range(n)):
			st.add(s[i])
			d_rev[i] = len(st)
		for i in range(n - 1):
			ans = d[i] + d_rev[i + 1]
			if ans > mx:
				mx = ans
		print(mx)
		t -= 1
solve()


def max_score(n, s):
	right = [0] + [0] * n
	cur_set = set()
	for i in reversed(range(n)):
		cur_set.add(s[i])
		right[i] = len(cur_set)
	cur_set = set()
	ans = 0
	for i in range(n):
		cur_set.add(s[i])
		ans = max(ans, len(cur_set) + right[i + 1])
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(max_score(n, s))


def func(n, s):
	m = 0
	firstDict = {}
	otherDict = {}
	firstLen = 0
	secLen = 0
	for i in s:
		if i in firstDict:
			firstDict[i] += 1
		else:
			firstDict[i] = 1
			firstLen += 1
	for i in s:
		if i in otherDict:
			otherDict[i] += 1
		else:
			otherDict[i] = 1
			secLen += 1
		if firstDict[i] == 1:
			firstLen -= 1
		if firstDict[i] > 0:
			firstDict[i] -= 1
		m = max(firstLen + secLen, m)
	print(m)
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	func(n, s)


import sys
input = sys.stdin.readline
f = lambda : map(int, input().split())
for _ in range(int(input())):
	N = int(input())
	X = input().strip()
	S = set()
	(A, B, C) = ([], [], [])
	for c in X:
		S.add(c)
		A.append(len(S))
	S = set()
	for c in X[::-1]:
		S.add(c)
		B.append(len(S))
	B = B[::-1]
	for i in range(N - 1):
		C.append(A[i] + B[i + 1])
	print(max(C))


import sys
sys_input = sys.stdin.readline
sys_print = sys.stdout.write

def ctoi(c):
	return ord(c) - 97

def single_case():
	n = int(sys_input())
	s = sys_input().strip()
	pre = [0 for _ in range(26)]
	suf = [0 for _ in range(26)]
	n_pre = 0
	n_suf = 0
	pre[ctoi(s[0])] += 1
	n_pre += 1
	for c in s[1:]:
		i = ctoi(c)
		if suf[i] == 0:
			n_suf += 1
		suf[i] += 1
	mx = n_pre + n_suf
	for c in s[1:-1]:
		i = ctoi(c)
		if pre[i] == 0:
			n_pre += 1
		pre[i] += 1
		suf[i] -= 1
		if suf[i] == 0:
			n_suf -= 1
		mx = max(mx, n_pre + n_suf)
	sys_print(f'{mx}\n')
t = int(sys_input())
for _ in range(t):
	single_case()


import sys
input = sys.stdin.readline

def dist_num(a):
	lett_nm = ord('a')
	answ = 0
	for i in range(26):
		if chr(lett_nm + i) in a:
			answ += 1
	return answ

def solve_d():
	answ = 0
	n = int(input())
	s = input().strip()
	answ = dist_num(s[:1]) + dist_num(s[1:])
	my_dict = {}
	for c in s:
		if c not in my_dict:
			my_dict[c] = 1
		else:
			my_dict[c] += 1
	dict_2 = {}
	for i in range(n - 1):
		c = s[i]
		if c not in dict_2:
			dict_2[c] = 1
		else:
			dict_2[c] += 1
		if c in my_dict:
			if my_dict[c] == 1:
				del my_dict[c]
			else:
				my_dict[c] -= 1
		curr_answ = len(dict_2) + len(my_dict)
		answ = max(answ, curr_answ)
	return answ

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


def sol(n, s):
	right_start = 1
	left = set(s[:right_start])
	right = dict()
	for c in s[right_start:]:
		if c in right:
			right[c] += 1
		else:
			right[c] = 1
	res = len(left) + len(right)
	for c in s[1:n - 1]:
		left.add(c)
		if right[c] < 2:
			del right[c]
		else:
			right[c] -= 1
		res = max(res, len(left) + len(right))
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(sol(n, s))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	p = n * [0]
	s = input().strip()
	a = set()
	for (i, x) in enumerate(s):
		a.add(x)
		p[i] = len(a)
	a.clear()
	ans = 0
	for i in range(n - 1, 0, -1):
		a.add(s[i])
		ans = max(ans, len(a) + p[i - 1])
	print(ans)


def solve(s):
	n = len(s)
	pref = [0] * n
	suf = [0] * n
	left = set()
	right = set()
	for i in range(n):
		left.add(s[i])
		pref[i] = len(left)
	for i in range(n - 1, -1, -1):
		right.add(s[i])
		suf[i] = len(right)
	ans = 0
	for i in range(n - 1):
		ans = max(ans, pref[i] + suf[i + 1])
	return ans
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = input().strip()
	print(solve(s))


t = int(input())

def solve():
	L = int(input())
	s = input().strip('\n')
	(first, second) = (dict(), dict())
	ans = 0
	for i in range(L):
		if s[i] not in second:
			second[s[i]] = 1
		else:
			second[s[i]] += 1
	for i in range(L):
		letter = s[i]
		if letter not in first:
			first[letter] = 1
		else:
			first[letter] += 1
		if second[letter] == 1:
			del second[letter]
		else:
			second[letter] -= 1
		if len(first) + len(second) > ans:
			ans = len(first) + len(second)
	print(ans)
for i in range(t):
	solve()


import sys
sys.setrecursionlimit(10 ** 9)

def ds(S):
	ans = len(set(S))
	l1 = []
	l2 = []
	for j in set(S):
		if S.count(j) != 1:
			l1 += [S.find(j)]
			l2 += [n - S[::-1].find(j) - 1]
	if l1 != []:
		l = l1 + l2
		c = ans
		L = list(set(l).intersection(range(max(l1) + 1)))
		L.sort()
		for k in L:
			if k in l1:
				c += 1
				if c > ans:
					ans = c
			else:
				c -= 1
	return ans
for i in range(int(input())):
	n = int(input())
	s = input()
	print(ds(s))


def func(s):
	d = {}
	firstCount = 0
	secCount = 0
	for i in s:
		if i not in d:
			secCount += 1
			d[i] = [1, False]
		else:
			d[i][0] += 1
	maxm = 0
	for j in range(len(s) - 1):
		i = s[j]
		d[i][0] -= 1
		if d[i][1] == False:
			firstCount += 1
			d[i][1] = True
		if d[i][0] == 0:
			secCount -= 1
		if maxm < firstCount + secCount:
			maxm = firstCount + secCount
	print(maxm)
	return
for _ in range(int(input())):
	n = int(input())
	func(input())


def solve(n, s):
	freqs = {}
	for i in s:
		freqs[i] = freqs.get(i, 0) + 1
	currmax = len(freqs)
	st = set()
	for i in s:
		st.add(i)
		freqs[i] -= 1
		if freqs[i] == 0:
			del freqs[i]
		currmax = max(currmax, len(freqs) + len(st))
	return currmax
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


def forward(n, s):
	(match, k) = ('', 0)
	l = [0]
	for char in s:
		if char not in match:
			match = match + char
			k += 1
		l.append(k)
	return l

def backward(n, s):
	return forward(n, s[::-1])[::-1]

def add(l1, l2, n):
	result = []
	for i in range(n):
		result.append(l1[i] + l2[i])
	return result

def max_sum(n, s):
	return max(add(forward(n, s), backward(n, s), n + 1)[1:-1])
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(max_sum(n, s))


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()

def solve():
	n = ri()
	s = rs()
	sf = [0] * n
	pf = [0] * (n + 1)
	_set = set()
	for i in range(n):
		_set.add(s[i])
		sf[i] = len(_set)
	_set = set()
	for i in range(n - 1, -1, -1):
		_set.add(s[i])
		pf[i] = len(_set)
	ans = 0
	for i in range(n):
		ans = max(ans, sf[i] + pf[i + 1])
	return ans

def main():
	for _ in range(ri()):
		print(solve())
main()


def solve():
	n = int(input().strip())
	str = input().strip()
	prefix = [0] * n
	suffix = [0] * n
	se = set()
	for i in range(n):
		se.add(str[i])
		prefix[i] = len(se)
	se = set()
	for i in range(n - 1, -1, -1):
		se.add(str[i])
		suffix[i] = len(se)
	ans = 0
	maxo = 0
	for i in range(n - 1):
		ans = prefix[i] + suffix[i + 1]
		maxo = max(maxo, ans)
	print(maxo)
	return 0
test_cases = int(input().strip())
for _ in range(test_cases):
	solve()


class func:

	def solve(self, string: str) -> int:
		start = 1
		length = len(string) - 1
		stacks = []
		while start <= length:
			first = len(set(string[:start]))
			second = len(set(string[start:]))
			total = first + second
			stacks.append(total)
			start += 1
		return max(stacks)

	def solve_op(self, string: str) -> int:
		sets = set()
		prefix = [0] * len(string)
		suffix = [0] * len(string)
		ans = 0
		for i in range(0, len(string)):
			sets.add(string[i])
			prefix[i] = len(sets)
		sets.clear()
		for i in range(len(string) - 1, -1, -1):
			sets.add(string[i])
			suffix[i] = len(sets)
		for i in range(0, len(string) - 1):
			ans = max(prefix[i] + suffix[i + 1], ans)
		return ans
obj = func()
tcs = int(input())
for i in range(tcs):
	length = int(input())
	string = input()
	print(obj.solve_op(string))


from typing import *
from collections import *
from math import *
from functools import *
INF = 1061109567

def RI():
	return int(input())

def RAI():
	return [int(i) for i in input().split()]

def RAI_1():
	return [INF] + RAI()

def slove():
	n = RI()
	s = ' ' + input()
	f = [0] * (n + 2)
	g = [0] * (n + 2)
	cnt = set()
	for i in range(1, n + 1):
		cnt.add(s[i])
		f[i] = len(cnt)
	cnt = set()
	for i in range(n, 0, -1):
		cnt.add(s[i])
		g[i] = len(cnt)
	res = 0
	for i in range(1, n + 1):
		res = max(res, f[i] + g[i + 1])
	print(res)

def main():
	t = 1
	t = RI()
	for _ in range(t):
		slove()
main()


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

def solve(a, n):
	pre = [0] * n
	suf = [0] * n
	s = set()
	for i in range(n):
		s.add(a[i])
		pre[i] = len(s)
	s = set()
	ans = 0
	for i in range(n - 1, 0, -1):
		s.add(a[i])
		suf[i] = len(s)
		ans = max(ans, suf[i] + pre[i - 1])
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = input().strip()
	print(solve(a, n))


def dist(s, n):
	dp = {}
	for i in range(n - 1):
		if s[i] in dp:
			dp[s[i]] += 1
		else:
			dp[s[i]] = 1
	ans = 1 + len(dp)
	dp2 = {}
	dp2[s[n - 1]] = 1
	for j in range(n - 2, 0, -1):
		dp[s[j]] -= 1
		if dp[s[j]] == 0:
			del dp[s[j]]
		if s[j] in dp2:
			dp2[s[j]] += 1
		else:
			dp2[s[j]] = 1
		if len(dp) + len(dp2) > ans:
			ans = len(dp) + len(dp2)
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(dist(s, n))


def solve():
	n = int(input())
	s = input()
	l_to_r_set = set(s[0])
	l_to_r = [1]
	for i in range(1, n):
		l_to_r_set.add(s[i])
		l_to_r.append(len(l_to_r_set))
	r_to_l_set = set(s[-1])
	r_to_l = [1]
	for i in range(n - 2, -1, -1):
		r_to_l_set.add(s[i])
		r_to_l.append(len(r_to_l_set))
	r_to_l.reverse()
	ans = 0
	for i in range(n - 1):
		ans = max(ans, l_to_r[i] + r_to_l[i + 1])
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
from math import *
from collections import defaultdict, deque
input = sys.stdin.readline
mod = 10 ** 9 + 7
INF = 1061109567
N = int(2 * 10 ** 5 + 5)
LINF = 4557430888798830399

def solve():
	n = int(input())
	s = input()
	cnt2 = [0] * 26
	num2 = 0
	for i in range(n):
		idx = ord(s[i]) - ord('a')
		cnt2[idx] += 1
		if cnt2[idx] == 1:
			num2 += 1
	(num1, ans) = (0, 0)
	cnt1 = [0] * 26
	for i in range(n - 1):
		idx = ord(s[i]) - ord('a')
		cnt1[idx] += 1
		if cnt1[idx] == 1:
			num1 += 1
		cnt2[idx] -= 1
		if cnt2[idx] == 0:
			num2 -= 1
		ans = max(ans, num1 + num2)
	print(ans)
T = int(input())
for t in range(T):
	solve()


from collections import defaultdict

def ss():
	c = int(input())
	ans = 0
	s = input()
	a = set()
	b = set()
	cc = [0] * c
	for i in reversed(range(c)):
		b.add(s[i])
		cc[i] = len(b)
	for i in range(c - 1):
		a.add(s[i])
		ans = max(ans, len(a) + cc[i + 1])
	print(ans)
n = int(input())
for i in range(n):
	ss()


def split_string(s):
	freq = {}
	for c in s:
		freq[c] = freq.get(c, 0) + 1
	left_freq = {}
	left_count = 0
	right_freq = freq.copy()
	right_count = len(freq)
	max_sum = 0
	for i in range(1, len(s)):
		c = s[i - 1]
		left_freq[c] = left_freq.get(c, 0) + 1
		left_count += left_freq[c] == 1
		right_freq[c] -= 1
		right_count -= right_freq[c] == 0
		max_sum = max(max_sum, left_count + right_count)
	return max_sum
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	print(split_string(s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = [0] * n
	st = set()
	for i in range(n - 1, -1, -1):
		st.add(s[i])
		p[i] = len(st)
	st = set()
	ans = []
	for i in range(n - 1):
		st.add(s[i])
		ans += (len(st) + p[i + 1],)
	print(max(ans))


class Solution:

	def distinct(self, n, s):
		(left_pre, right_pre) = ([1], [1])
		(left_set, right_set) = (set(s[0]), set(s[-1]))
		for i in range(1, n):
			left_set.add(s[i])
			right_set.add(s[n - i - 1])
			left_pre.append(len(left_set))
			right_pre.append(len(right_set))
		right_pre = right_pre[::-1]
		ans = 0
		for i in range(1, n):
			ans = max(ans, left_pre[i - 1] + right_pre[i])
		return ans
sol = Solution()
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(sol.distinct(n, s))


from collections import defaultdict

def answer(string):
	(visitedleft, visitedright) = (set(), set())
	(prefixleft, prefixright) = ([0], [0])
	for i in range(len(string)):
		visitedleft.add(string[i])
		prefixleft.append(len(visitedleft))
	for i in range(len(string) - 1, -1, -1):
		visitedright.add(string[i])
		prefixright.append(len(visitedright))
	prefixright.reverse()
	result = 0
	for i in range(len(prefixleft)):
		result = max(result, prefixleft[i] + prefixright[i])
	return result
test = int(input())
for i in range(test):
	length = int(input())
	string = input()
	print(answer(string))


for _ in range(int(input())):
	a = int(input())
	b = input()
	fo = set()
	ba = set()
	lf = []
	lb = []
	for x in range(a - 1):
		fo.add(b[x])
		lf += [len(fo)]
	ba.add(b[a - 1])
	c = 1
	for x in range(a - 2, -1, -1):
		e = len(ba) + lf[x]
		if e > c:
			c = e
		ba.add(b[x])
	print(c)


def solve(string):
	has = set()
	left = [0] * len(string)
	for i in range(len(string)):
		if string[i] not in has:
			has.add(string[i])
		left[i] = len(has)
	right = [0] * len(string)
	has.clear()
	for i in range(len(string) - 1, -1, -1):
		if string[i] not in has:
			has.add(string[i])
		right[i] = len(has)
	ans = 0
	for i in range(len(string) - 1):
		ans = max(ans, left[i] + right[i + 1])
	return ans

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


t = int(input())
for _ in range(t):
	n = int(input())
	a = list()
	s = input()
	q = set()
	v = set()
	for i in range(n):
		q.add(s[i])
		a.append(len(q))
	mx = a[-1]
	for i in range(n - 1, -1, -1):
		v.add(s[i])
		if i > 0:
			d = len(v) + a[i - 1]
		else:
			d = len(v)
		if d > mx:
			mx = d
	print(mx)


import sys
input = sys.stdin.readline
T = int(input())
result = []
for _ in range(T):
	N = int(input())
	dic = {chr(i): 0 for i in range(97, 123)}
	arr = list(input().rstrip())
	for i in range(N):
		dic[arr[i]] += 1
	L = set()
	R = set(arr)
	res = 0
	for i in arr:
		L.add(i)
		dic[i] -= 1
		if dic[i] == 0:
			R.remove(i)
		res = max(res, len(L) + len(R))
	result.append(res)
print('\n'.join(map(str, result)))


import sys, os
TC = True

def solve():
	n = int(input())
	s = input()
	mp1 = {}
	mp2 = {}
	arr1 = [0] * n
	arr2 = [0] * n
	arr1[0] = 1
	mp1[s[0]] = 1
	for i in range(1, n):
		if s[i] in mp1:
			arr1[i] = arr1[i - 1]
		else:
			arr1[i] = arr1[i - 1] + 1
			mp1[s[i]] = 1
	arr2[n - 1] = 1
	mp2[s[n - 1]] = 1
	for i in range(n - 2, -1, -1):
		if s[i] in mp2:
			arr2[i] = arr2[i + 1]
		else:
			arr2[i] = arr2[i + 1] + 1
			mp2[s[i]] = 1
	ans = 0
	for i in range(n - 1):
		ans = max(ans, arr1[i] + arr2[i + 1])
	print(ans)
if os.path.exists('input.txt'):
	debug = True
	sys.stdin = open('input.txt', 'r')
if TC:
	for _ in range(int(input())):
		solve()
else:
	solve()


from collections import Counter

def main():
	cases = int(input())
	while cases > 0:
		n = int(input())
		a = list(input())
		(c, ans) = (1, 0)
		count1 = []
		count2 = []
		(l, r) = (set(), set())
		for i in range(n):
			l.add(a[i])
			r.add(a[n - 1 - i])
			count1.append(len(l))
			count2.append(len(r))
		for i in range(n - 1):
			ans = max(ans, count1[i] + count2[n - i - 2])
		print(ans)
		cases -= 1
	return 0
main()


def solve(s):
	prefix = []
	suffix = []
	visited1 = set()
	visited2 = set()
	for i in range(len(s)):
		visited1.add(s[i])
		visited2.add(s[-i - 1])
		prefix.append(len(visited1))
		suffix.append(len(visited2))
	suffix.reverse()
	ans = 0
	for i in range(len(s) - 1):
		ans = max(prefix[i] + suffix[i + 1], ans)
	return ans
for _ in range(int(input())):
	(_, s) = (input(), input())
	print(solve(s))


def sol(a, b):
	set1 = set()
	set2 = set()
	prefix = []
	suffix = []
	for i in range(a):
		set1.add(b[i])
		set2.add(b[n - i - 1])
		prefix.append(len(set1))
		suffix.append(len(set2))
	res = 0
	for i in range(a - 1):
		res = max(res, prefix[i] + suffix[a - i - 2])
	return res
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(sol(n, s))


def uniqalc(s, n):
	d1 = set()
	d2 = set()
	max_ = 0
	z1 = [0] * n
	z2 = [0] * n
	for i in range(n):
		d1.add(s[i])
		d2.add(s[n - 1 - i])
		z1[i] = len(d1)
		z2[n - 1 - i] = len(d2)
	for i in range(n - 1):
		max_ = max(max_, z1[i] + z2[i + 1])
	return max_
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(uniqalc(s, n))


def f(x, s):
	D = {}
	L = [0] * x
	L[0] = 1
	D[s[0]] = 1
	for i in range(1, x):
		if s[i] not in D:
			D[s[i]] = 1
			L[i] = L[i - 1] + 1
		else:
			L[i] = L[i - 1]
	L2 = [0] * x
	L2[-1] = 1
	D2 = {s[-1]: 1}
	for i in range(x - 2, -1, -1):
		if s[i] not in D2:
			D2[s[i]] = 1
			L2[i] = L2[i + 1] + 1
		else:
			L2[i] = L2[i + 1]
	ans = 0
	for i in range(x - 1):
		curr = L[i] + L2[i + 1]
		ans = max(ans, curr)
	return ans
t = int(input())
for i in range(t):
	x = int(input())
	L = input()
	print(f(x, L))


def sol(n, s):
	(suf, pref) = ([0] * n, [0] * n)
	st = set()
	for i in range(n):
		st.add(s[i])
		pref[i] = len(st)
	st = set()
	for i in range(n - 1, -1, -1):
		st.add(s[i])
		suf[i] = len(st)
	Max = 0
	for i in range(n - 1):
		a = pref[i] + suf[i + 1]
		Max = max(a, Max)
	return Max
t = int(input())
while t:
	n = int(input())
	s = input()
	print(sol(n, s))
	t -= 1


t = int(input())

def zrataj(s):
	pismenka = set()
	res = [0 for _ in range(len(s) + 1)]
	for i in range(len(s)):
		pismenka.add(s[i])
		res[i + 1] = len(pismenka)
	return res

def solve():
	n = int(input())
	s = input()
	spredu = zrataj(s)
	zozadu = zrataj(s[::-1])
	zozadu = zozadu[::-1]
	best = 0
	for i in range(n + 1):
		best = max(best, spredu[i] + zozadu[i])
	print(best)
for _ in range(t):
	solve()


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	a = set()
	b = set()
	la = [0]
	ans = 0
	for j in range(m - 1):
		a.add(s[j])
		la.append(len(a))
	for j in range(m - 1, 0, -1):
		b.add(s[j])
		ans = max(ans, la[j] + len(b))
	print(ans)


t = int(input())
for _ in range(t):
	l = int(input())
	s = input()
	prefix = [0]
	chars = set()
	for i in range(l):
		if s[i] not in chars:
			chars.add(s[i])
			prefix.append(prefix[i] + 1)
		else:
			prefix.append(prefix[i])
	res = 0
	postfix = 0
	chars = set()
	for i in range(l - 1, -1, -1):
		if s[i] not in chars:
			chars.add(s[i])
			postfix += 1
		if prefix[i] + postfix > res:
			res = prefix[i] + postfix
	print(res)


import sys
lines = list(map(str.strip, sys.stdin.readlines()))
for s in lines[2::2]:
	counts = {}
	for c in s:
		counts[c] = counts.get(c, 0) + 1
	othercounts = {}
	result = 0
	for c in s:
		othercounts[c] = othercounts.get(c, 0) + 1
		counts[c] -= 1
		if counts[c] == 0:
			del counts[c]
		result = max(result, len(counts) + len(othercounts))
	print(result)


t = int(input())
for _ in range(t):
	_ = input()
	s = input()
	left = []
	curset = set()
	for c in s:
		curset.add(c)
		left.append(len(curset))
	curset = set()
	right = []
	for c in s[::-1]:
		curset.add(c)
		right.append(len(curset))
	right = right[::-1]
	maxi = 0
	for i in range(len(s) - 1):
		t = left[i] + right[i + 1]
		if t > maxi:
			maxi = t
	print(maxi)


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()
	suff = [0] * n
	pref = [0] * n
	net = {s[0]}
	pref[0] = 1
	for i in range(1, n):
		c = s[i]
		if c in net:
			pref[i] = pref[i - 1]
		else:
			pref[i] = 1 + pref[i - 1]
			net.add(c)
	net = {s[-1]}
	suff[-1] = 1
	for j in range(n - 2, -1, -1):
		c = s[j]
		if c in net:
			suff[j] = suff[j + 1]
		else:
			suff[j] = 1 + suff[j + 1]
			net.add(c)
	maxi = 0
	for i in range(1, n):
		one = pref[i - 1]
		two = suff[i]
		maxi = max(maxi, one + two)
	print(maxi)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	left_dictionary = {}
	right_dictionary = set()
	for letter in s:
		if letter in left_dictionary:
			left_dictionary[letter] += 1
		else:
			left_dictionary[letter] = 1
	ans = len(left_dictionary)
	for letter in s:
		current = len(left_dictionary) + len(right_dictionary)
		if left_dictionary[letter] == 1:
			left_dictionary.pop(letter)
			if letter not in right_dictionary:
				right_dictionary.add(letter)
			else:
				ans = max(ans, current - 1)
		else:
			left_dictionary[letter] -= 1
			if letter not in right_dictionary:
				right_dictionary.add(letter)
				ans = max(ans, current + 1)
	print(ans)


cases = int(input())
for _ in range(cases):
	N = int(input())
	s = input()
	counts = [0 for x in range(N - 1)]
	l = set()
	r = set()
	for (i, x) in enumerate(s[:-1]):
		l.add(x)
		counts[i] += len(l)
	for (i, x) in enumerate(reversed(s[1:])):
		r.add(x)
		counts[N - 2 - i] += len(r)
	print(max(counts))


tc = int(input())
res = []
for i in range(tc):
	n = int(input())
	st = input()
	mp1 = set()
	ltr = []
	x = 0
	y = 0
	for i in st:
		if i not in mp1:
			x += 1
			mp1.add(i)
			ltr.append(x)
		else:
			ltr.append(x)
	x = 0
	mp1.clear()
	rtl = []
	for i in st[::-1]:
		if i not in mp1:
			x += 1
			mp1.add(i)
			rtl.append(x)
		else:
			rtl.append(x)
	rtl = rtl[::-1]
	i = 0
	maxval = 0
	while i < len(rtl) - 1:
		maxval = max(maxval, ltr[i] + rtl[i + 1])
		i += 1
	res.append(maxval)
for i in res:
	print(i)


from collections import Counter

def func(s):
	dc1 = Counter(s)
	dc2 = {}
	(n1, n2, ans) = (len(dc1), 0, 0)
	for i in s:
		if i not in dc2:
			dc2[i] = 1
			n2 += 1
		else:
			dc2[i] += 1
		dc1[i] -= 1
		if dc1[i] == 0:
			n1 -= 1
		ans = max(ans, n1 + n2)
	return ans

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


n = int(input())
a = 0
s = 0
f = []
h = set()
k = []
d = set()
for i in range(n):
	m = int(input())
	t = input()
	for j in t:
		h.add(j)
		f.append(len(h))
	t = t[::-1]
	for l in t:
		d.add(l)
		k.append(len(d))
	k = k[::-1]
	for q in range(m - 1):
		a = f[q] + k[q + 1]
		if a > s:
			s = a
	print(s)
	a = 0
	s = 0
	f = []
	h = set()
	k = []
	d = set()


import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	(n, s, d) = (int(input()), input(), dict())
	for c in s:
		if c not in d:
			d[c] = 0
		d[c] += 1
	(b, al, ret) = (set(), len(d), len(d))
	for i in range(n):
		b.add(s[i])
		d[s[i]] -= 1
		if d[s[i]] == 0:
			al -= 1
		ret = max(len(b) + al, ret)
	print(ret)


import sys
n = int(next(sys.stdin))
for _ in range(n):
	l = int(next(sys.stdin))
	s = next(sys.stdin).strip()
	l_f = set()
	forward = [26] * len(s)
	c_f = 0
	l_b = set()
	backward = [26] * len(s)
	c_b = 0
	for i in range(l):
		if c_f < 26:
			if not s[i] in l_f:
				l_f.add(s[i])
				c_f += 1
			forward[i] = c_f
		if c_b < 26:
			b = l - 1 - i
			if not s[b] in l_b:
				l_b.add(s[b])
				c_b += 1
			backward[b] = c_b
	m = backward[0]
	for i in range(l - 1):
		x = backward[i + 1] + forward[i]
		if x > m:
			m = x
		if m == 52:
			break
	print(m)


import sys, math, bisect, collections, itertools, heapq
from collections import defaultdict, deque
sys.setrecursionlimit(50000)
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	l = list(sys.stdin.readline().strip())
	mySet1 = set()
	res = len(set(l))
	for (i, vl) in enumerate(l):
		if vl not in mySet1:
			mySet1.add(vl)
			res = max(len(mySet1) + len(set(l[i + 1:])), res)
	print(res)


n = int(input())
words = []
for i in range(n):
	s = int(input())
	st = str(input())
	words.append(st)
for word in words:
	all = {}
	cur = {}
	for c in word:
		if c in all:
			all[c] += 1
		else:
			all[c] = 1
	ans = 0
	for c in word:
		if c in cur:
			cur[c] += 1
		else:
			cur[c] = 1
		all[c] -= 1
		if all[c] == 0:
			all.pop(c)
		ans = max(ans, len(all) + len(cur))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	S = input()
	set1 = set()
	set2 = set()
	izq = []
	der = []
	for i in S:
		set1.add(i)
		izq.append(len(set1))
	for i in range(n - 1, -1, -1):
		set2.add(S[i])
		der.append(len(set2))
	mayor = 2
	f = n - 2
	for i in range(0, n - 1):
		if izq[i] + der[f - i] > mayor:
			mayor = izq[i] + der[f - i]
	print(mayor)


for z in range(int(input())):
	n = int(input())
	s = input()
	a = []
	b = []
	s1 = set()
	for i in range(0, n - 1):
		s1.add(s[i])
		a.append(len(s1))
	s1.clear()
	for j in range(n - 1, 0, -1):
		s1.add(s[j])
		b.append(len(s1))
	b = b[::-1]
	ma = -1
	for i in range(n - 1):
		if a[i] + b[i] > ma:
			ma = a[i] + b[i]
	print(ma)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ori = {}
	for m in s:
		if m not in ori:
			ori[m] = 1
		else:
			ori[m] += 1
	f1 = {}
	maxi = len(ori)
	c = 0
	ans = 0
	for m in s:
		ori[m] -= 1
		if ori[m] == 0:
			maxi -= 1
		if m not in f1:
			c += 1
			f1[m] = 1
		ans = max(ans, c + maxi)
	print(ans)


for _ in range(int(input())):
	a = int(input())
	s = input()
	dic = {}
	left = []
	right = [0] * a
	c = 0
	for i in s:
		if i not in dic:
			c += 1
			dic[i] = 1
		left.append(c)
	c = 0
	dic = {}
	for i in range(a - 1, -1, -1):
		left[i] += c
		if s[i] in dic:
			continue
		else:
			dic[s[i]] = 1
			c += 1
	print(max(left))


for t in range(int(input())):
	n = int(input())
	s = input()
	lst = []
	st = set()
	for i in range(n):
		st.add(s[i])
		lst.append(len(st))
	st = set()
	flc = -1
	for j in range(n - 1, 0, -1):
		st.add(s[j])
		flc = max(flc, len(st) + lst[j - 1])
	print(flc)


from collections import Counter

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

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

def insr():
	s = input()
	return s
t = inp()
for _ in range(t):
	n = inp()
	s = insr()
	pre = []
	found = set()
	for char in s:
		found.add(char)
		pre.append(len(found))
	sfound = set()
	ans = 0
	for i in range(n - 1, 0, -1):
		sfound.add(s[i])
		ans = max(ans, pre[i - 1] + len(sfound))
	print(ans)


n = int(input())
for i in range(n):
	l = int(input())
	s = input()
	fs = [-1000 for i in range(l + 1)]
	d = {}
	for i in range(l):
		d[s[i]] = 0
		fs[i + 1] = len(d)
	d = {}
	fe = [-1000 for i in range(l + 1)]
	for i in range(l - 1, 0, -1):
		d[s[i]] = 0
		fe[i] = len(d)
	b = 1
	for i in range(l):
		if fs[i] + fe[i] > b:
			b = fs[i] + fe[i]
	print(b)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	s = input()[:-1]
	sa = {s[0]: 1}
	sb = {}
	for i in range(1, len(s)):
		sb[s[i]] = sb.get(s[i], 0) + 1
	a = 1
	b = len(sb)
	m = a + b
	for i in range(1, len(s)):
		sa[s[i]] = sa.get(s[i], 0) + 1
		if sb[s[i]] != 1:
			sb[s[i]] -= 1
		else:
			sb.pop(s[i])
		m = max(m, len(sa) + len(sb))
	print(m)


for i in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	d1 = {}
	res = len(d)
	for i in s:
		d[i] -= 1
		d1[i] = 1
		if d[i] == 0:
			del d[i]
		res = max(res, len(d) + len(d1))
	print(res)


times = int(input())
for _ in range(times):
	length = int(input())
	st = input()
	graph = {}
	for i in range(len(st)):
		if st[i] in graph:
			graph[st[i]][1] = i
		else:
			graph.update({st[i]: [i, i]})
	s = [0] * len(st)
	for i in graph:
		s[graph[i][0]] += 1
		s[graph[i][1]] -= 1
	mymax = len(graph)
	addition = len(graph)
	for i in s:
		addition += i
		if mymax < addition:
			mymax = addition
	print(mymax)


from collections import defaultdict

def solve():
	n = int(input())
	s = input().strip()
	cnt1 = defaultdict(int)
	cnt2 = defaultdict(int)
	res = 0
	for c in s:
		res += not cnt2[c]
		cnt2[c] += 1
	ans = res
	for c in s:
		res -= cnt2[c] == 1
		cnt2[c] -= 1
		res += not cnt1[c]
		cnt1[c] += 1
		ans = max(ans, res)
	print(ans)
T = int(input())
for _ in range(T):
	solve()


t = int(input())
while t:
	n = int(input())
	s = input()
	d = dict()
	d1 = dict()
	for i in range(1, n):
		d[s[i]] = d.get(s[i], 0) + 1
	d1[s[0]] = 1
	ans = 1 + len(d)
	c = 0
	for i in range(1, n):
		if s[i] not in d1:
			d1[s[i]] = 1
		if d[s[i]] == 1:
			del d[s[i]]
		else:
			d[s[i]] -= 1
		c = len(d) + len(d1)
		if ans < c:
			ans = c
	print(ans)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	hmap = {}
	for c in s:
		if c not in hmap:
			hmap[c] = 0
		hmap[c] += 1
	res = 0
	dis = set()
	for c in s:
		dis.add(c)
		hmap[c] -= 1
		if hmap[c] == 0:
			del hmap[c]
		res = max(res, len(dis) + len(hmap))
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	dica = dict()
	dicb = dict()
	ans = -1
	suma = 0
	sumb = 0
	for i in s:
		if i in dicb.keys():
			dicb[i] += 1
		else:
			dicb[i] = 1
			sumb += 1
	for i in s:
		if ans < suma + sumb:
			ans = suma + sumb
		if i in dica.keys():
			if dicb[i] > 1:
				dicb[i] -= 1
			elif dicb[i] == 1:
				del dicb[i]
				sumb -= 1
			continue
		else:
			dica[i] = 1
			suma += 1
			if dicb[i] > 1:
				dicb[i] -= 1
			elif dicb[i] == 1:
				del dicb[i]
				sumb -= 1
	print(ans)


for _ in range(int(input())):
	lth = int(input())
	s = input()
	bDict = {}
	aSet = set()
	maxx = 0
	for ch in s:
		if ch in bDict:
			bDict[ch] += 1
		else:
			bDict[ch] = 1
	for ch in s:
		aSet.add(ch)
		bDict[ch] -= 1
		if bDict[ch] == 0:
			del bDict[ch]
		maxx = max(maxx, len(aSet) + len(bDict))
	print(maxx)


def solve(s):
	dp1 = [1 for _ in range(len(s))]
	dp2 = [1 for _ in range(len(s))]
	all_chars = set()
	all_chars.add(s[0])
	for i in range(1, len(s)):
		if s[i] in all_chars:
			dp1[i] = dp1[i - 1]
		else:
			all_chars.add(s[i])
			dp1[i] = dp1[i - 1] + 1
	all_chars = set()
	all_chars.add(s[-1])
	for j in range(len(s) - 2, -1, -1):
		if s[j] in all_chars:
			dp2[j] = dp2[j + 1]
		else:
			all_chars.add(s[j])
			dp2[j] = dp2[j + 1] + 1
	val = 0
	for i in range(len(s) - 1):
		val = max(val, dp1[i] + dp2[i + 1])
	print(val)
n = int(input())
for _ in range(n):
	q = int(input())
	s = input()
	solve(s)


t = int(input())
from collections import Counter
from time import time

def solution(path: str):
	ans = -1
	aDict = dict()
	aCounter = 0
	pathDict = Counter(path)
	bCounter = len(pathDict.keys())
	for i in path:
		iInA = aDict.get(i, None)
		if iInA is None:
			aCounter += 1
			aDict[i] = 1
		iInB = pathDict.get(i, 0)
		if iInB > 0:
			if iInB == 1:
				bCounter -= 1
			pathDict[i] -= 1
		ans = max(ans, aCounter + bCounter)
	return ans
while t > 0:
	n = int(input())
	print(solution(input()))
	t -= 1


queries = int(input())
for i in range(queries):
	n = int(input())
	s = input()
	D = {}
	for j in range(n):
		if s[j] not in D:
			D[s[j]] = 1
		else:
			D[s[j]] += 1
	f1 = 0
	f2 = len(D.keys())
	D2 = {}
	maxval = 0
	for j in range(n):
		D[s[j]] -= 1
		if D[s[j]] == 0:
			f2 -= 1
		if s[j] not in D2:
			D2[s[j]] = 1
			f1 += 1
		else:
			D2[s[j]] += 1
		current = f1 + f2
		if current > maxval:
			maxval = current
	print(maxval)


for _ in range(int(input())):
	n = int(input())
	s = input()

	def getPrefix(st):
		chars = set()
		prefixCount = [0] * n
		prefixCount[0] = 1
		chars.add(st[0])
		for i in range(1, n):
			if st[i] in chars:
				prefixCount[i] = prefixCount[i - 1]
			else:
				prefixCount[i] = prefixCount[i - 1] + 1
				chars.add(st[i])
		return prefixCount
	prefixArr = getPrefix(s)
	suffixArr = getPrefix(s[::-1])
	ans = -1
	for i in range(0, n - 1):
		ans = max(ans, prefixArr[i] + suffixArr[n - (i + 1) - 1])
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	m = {}
	for i in s:
		if m.get(i) == None:
			m[i] = 1
		else:
			m[i] += 1
	a = 0
	b = len(m.keys())
	ma = {}
	res = 0
	for i in s:
		if ma.get(i) == None:
			a += 1
			ma[i] = 1
		if m.get(i) == 1:
			b -= 1
		m[i] -= 1
		res = max(res, a + b)
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	distinct_start = 0
	distinct_end = 0
	chars_start = {}
	chars_end = {}
	for c in s:
		if c in chars_end:
			chars_end[c] += 1
		else:
			chars_end[c] = 1
			distinct_end += 1
	maximum_sum = 0
	for c in s:
		if c in chars_start:
			chars_start[c] += 1
		else:
			chars_start[c] = 1
			distinct_start += 1
		chars_end[c] -= 1
		if chars_end[c] == 0:
			distinct_end -= 1
		maximum_sum = max(maximum_sum, distinct_start + distinct_end)
	print(maximum_sum)


def solve():
	n = int(input())
	s = str(input())
	d1 = {}
	d2 = {}
	d1[s[0]] = 1
	for i in range(1, n):
		d2.setdefault(s[i], 0)
		d2[s[i]] += 1
	max_val = len(d1) + len(d2)
	for i in range(1, n):
		d2[s[i]] -= 1
		d1.setdefault(s[i], 0)
		d1[s[i]] += 1
		if d2.get(s[i]) == 0:
			d2.pop(s[i])
		max_val = max(max_val, len(d1) + len(d2))
	print(max_val)
t = int(input())
for _ in range(t):
	solve()


from collections import Counter
from collections import defaultdict

def maxSplit(nums):
	count = Counter(nums)
	dic = defaultdict(int)
	res = 0
	for num in nums:
		dic[num] += 1
		count[num] -= 1
		if count[num] == 0:
			count.pop(num)
		res = max(res, len(count) + len(dic))
	return res
case = int(input())
for i in range(case):
	length = input()
	pos = input()
	print(maxSplit(pos))


from collections import deque

def solve():
	n = int(input())
	s = input()
	a = set()
	b = dict()
	B = 0
	for i in range(n):
		if b.get(s[i], -1) == -1:
			b[s[i]] = deque()
			B += 1
		b[s[i]].append(i)
	res = -1
	for i in range(1, n):
		a.add(s[i - 1])
		b[s[i - 1]].popleft()
		if len(b[s[i - 1]]) == 0:
			B -= 1
		res = max(res, len(a) + B)
	print(res)
t = int(input())
for _ in range(t):
	solve()


import sys
N = int(200000.0 + 5)
sys.setrecursionlimit(N)

def charming():
	n = int(input())
	s = '#' + input()
	pre = [0] * (n + 5)
	suf = [0] * (n + 5)
	vis1 = set()
	vis2 = set()
	for i in range(1, n + 1):
		pre[i] = pre[i - 1]
		if s[i] not in vis1:
			pre[i] += 1
			vis1.add(s[i])
	for i in range(n, 0, -1):
		suf[i] = suf[i + 1]
		if s[i] not in vis2:
			suf[i] += 1
			vis2.add(s[i])
	res = 1
	for i in range(1, n):
		res = max(res, pre[i] + suf[i + 1])
	print(res)
for t in range(int(input())):
	charming()


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	word = list(input())
	dic = defaultdict(int)
	a = set()
	ans = 0
	for w in word:
		dic[w] += 1
	for w in word:
		a.add(w)
		dic[w] -= 1
		if dic[w] == 0:
			del dic[w]
		ans = max(ans, len(a) + len(dic))
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	prefix = []
	suffix = []
	temp = set()
	for char in s:
		temp.add(char)
		prefix.append(len(temp))
	temp = set()
	for char in s[-1::-1]:
		suffix.append(len(temp))
		temp.add(char)
	res = 0
	suffix = suffix[-1::-1]
	for idx in range(n):
		res = max(res, prefix[idx] + suffix[idx])
	print(res)


def cuddle():
	n = int(input().strip())
	s = input().strip()
	mia = {}
	mpia = {}
	vector1 = []
	vector2 = []
	for i in range(n):
		if s[i] in mia:
			mia[s[i]] += 1
		else:
			mia[s[i]] = 1
		vector1.append(len(mia))
	for i in range(n - 1, -1, -1):
		if s[i] in mpia:
			mpia[s[i]] += 1
		else:
			mpia[s[i]] = 1
		vector2.append(len(mpia))
	maxima = 0
	for i in range(n - 1):
		maxima = max(maxima, vector1[i] + vector2[n - i - 2])
	print(maxima)
for _ in range(int(input())):
	cuddle()


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	s = input()
	left = [0] * n
	right = [0] * n
	l = set()
	r = set()
	for i in range(n):
		l.add(s[i])
		left[i] = len(l)
	for i in range(n - 1, -1, -1):
		r.add(s[i])
		right[i] = len(r)
	result = -1000000000.0
	for i in range(n - 1):
		result = max(result, left[i] + right[i + 1])
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	v = 0
	a_list = [0] * 26
	a_total = 0
	b_list = [0] * 26
	b_total = 0
	for x in s:
		a_list[ord(x) - 97] += 1
	for x in a_list:
		if x != 0:
			a_total += 1
	v = a_total
	for x in s:
		p = ord(x) - 97
		a_list[p] -= 1
		b_list[p] += 1
		if a_list[p] == 0:
			a_total -= 1
		if b_list[p] == 1:
			b_total += 1
			if v < a_total + b_total:
				v = a_total + b_total
				if v == 52:
					break
	print(v)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	setn = set()
	setm = set()
	s1 = [0] * n
	s2 = [0] * n
	maxn = 0
	for i in range(n):
		setn.add(s[i])
		s1[i] = len(setn)
	for j in range(n - 1, -1, -1):
		if j == 0:
			if s2[j] > maxn:
				maxn = s2[j]
		else:
			setm.add(s[j])
			s2[j] = len(setm)
			if s1[j - 1] + s2[j] > maxn:
				maxn = s1[j - 1] + s2[j]
	print(maxn)


for t in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	for i in s:
		d[i] = d.get(i, 0) + 1
	z = len(d)
	ans = 0
	l = set()
	for i in range(n):
		l.add(s[i])
		d[s[i]] -= 1
		z -= 1 if d[s[i]] == 0 else 0
		ans = max(ans, z + len(l))
	print(ans)


for i in range(int(input())):
	len1 = int(input())
	str1 = input()
	(sum1, sum2, total) = (1, 0, 0)
	(dict1, dict2) = ({str1[0]: 1}, {})
	for i in range(1, len1):
		if str1[i] in dict2:
			dict2[str1[i]] += 1
		else:
			dict2[str1[i]] = 1
			sum2 += 1
	total = sum1 + sum2
	for i in range(1, len1 - 1):
		if str1[i] not in dict1:
			sum1 += 1
			dict1[str1[i]] = 1
		dict2[str1[i]] -= 1
		if dict2[str1[i]] == 0:
			sum2 -= 1
		total = max(total, sum1 + sum2)
	print(total)