We need to split the string \( s \) into two non-empty parts \( a \) and \( b \) such that the sum of distinct characters in both parts is maximized. The key observation here is that we can efficiently track the distinct characters in both parts as we move through the string. We can solve this problem by iterating over each character of the string and keeping track of two sets:

• One set for characters in the left part (which means for \( a \)).
• One set for characters in the right part (which means for \( b \)).

• Start by putting all characters in the right part of the string.
• Iterate through each character in the string, shifting one character at a time from the right part to the left part, and updating the distinct character counts for both parts.
• At each step, compute the sum of distinct characters in both parts and keep track of the maximum sum observed.

from collections import Counter

def max_distinct_split(s):
    right_counter = Counter(s)  # Tracks character counts in the right part
    left_counter = Counter()    # Tracks character counts in the left part
    max_distinct_sum = 0        # Stores the maximum sum of distinct characters

    for char in s:
        # Move character from right part to left part
        left_counter[char] += 1
        right_counter[char] -= 1

        # If a character count in the right part becomes zero, remove it
        if right_counter[char] == 0:
            del right_counter[char]

        # Calculate the sum of distinct characters in both parts
        distinct_sum = len(left_counter) + len(right_counter)
        max_distinct_sum = max(max_distinct_sum, distinct_sum)

    return max_distinct_sum


t = int(input())

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