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$

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$.