CF1907C.Removal of Unattractive Pairs

Vlad found a string $s$ consisting of $n$ lowercase Latin letters, and he wants to make it as short as possible.

To do this, he can remove any pair of adjacent characters from $s$ any number of times, provided they are different. For example, if $s$=racoon, then by removing one pair of characters he can obtain the strings coon, roon, raon, and raco, but he cannot obtain racn (because the removed letters were the same) or rcon (because the removed letters were not adjacent).

What is the minimum length Vlad can achieve by applying any number of deletions?

弗拉德找到了一个由 $n$ 个小写拉丁字母组成的字符串 $s$，他希望将其尽可能缩短。

为此，他可以任意次地从 $s$ 中删除任意一对相邻字符，但前提是这两个字符互不相同。例如，若 $s = \text{racoon}$，则通过删除一对字符，他可以得到字符串 $\text{coon}$、$\text{roon}$、$\text{raon}$ 和 $\text{raco}$，但他无法得到 $\text{racn}$（因为被删去的两个字母相同），也无法得到 $\text{rcon}$（因为被删去的两个字母不相邻）。

通过任意次数的删除操作，弗拉德所能达到的最短长度是多少？

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains the string $s$ consisting of $n$ lowercase Latin letters.

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

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $s$。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a single number—the minimum length of the string $s$, after removing pairs of adjacent characters with different values.

对于每个测试用例，输出一个数字——字符串 $s$ 在删除所有相邻且值不同的字符对之后的最小长度。

In the first test case of the example, you need to act as follows: "aabc" $\rightarrow$ "ac" $\rightarrow$ "". Note that with a different order of deletions, the string will not become empty.

在示例的第一个测试用例中，你需要按如下方式操作：“aabc” $\rightarrow$ “ac” $\rightarrow$ “”。注意，若以不同的顺序进行删除，字符串将无法变为空。