Deletion 2

You are given a string $S$ of length $N$. $S$ consists only of $\texttt{A}$, $\texttt{B}$, and $\texttt{C}$.

In one operation, choose two adjacent different characters and delete both of them. The remaining parts are concatenated.

Repeat the operation until no operation is possible. Find the number of distinct strings that can remain. The empty string is also counted.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $S$

For each test case, print the number of distinct possible final strings on one line.

• $1 \le T \le 2\,000\,000$.
• $1 \le N \le 2\,000\,000$.
• $S$ is a string of length $N$ consisting only of $\texttt{A}$, $\texttt{B}$, and $\texttt{C}$.
• The sum of $N$ over all test cases does not exceed $2\,000\,000$.