CF1907C Removal of Unattractive Pairs

Vlad 找到一个由 $n$ 个小写拉丁字母组成的字符串 $s$，他希望将其尽可能缩短。 为此，他可以任意次数地删除任意一对相邻且不同的字符。例如，如果 $s$ = racoon，那么通过删除一对字符，他可以得到 coon、roon、raon 和 raco，但不能得到 racn（因为被删除的字母相同）或 rcon（因为被删除的字母不是相邻的）。 通过任意次数的删除操作，Vlad 最终能得到的字符串的最小长度是多少？

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。 每个测试用例的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示通过删除任意数量的相邻且不同的字符对后，字符串 $s$ 能达到的最小长度。

在示例的第一个测试用例中，你需要这样操作："aabc" $\rightarrow$ "ac" $\rightarrow$ ""。注意，如果删除的顺序不同，字符串可能不会变为空串。 由 ChatGPT 4.1 翻译