该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：pair.in

输出：pair.out

题目描述

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$ 能达到的最小长度。

输入输出样例

10
4
aabc
5
abaca
10
avbvvcvvvd
7
abcdefg
5
dabbb
8
aacebeaa
7
bbbbacc
6
dacfcc
6
fdfcdc
9
dbdcfbbdc

0
1
2
1
1
0
1
0
0
1

说明/提示

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