Reversal ABC

Input

The first line contains one integer $T$ (1\le T\le 10^5) — the number of sets of input data. The description of the input data sets follows.

In the first line of each input data set, there is one integer $n$ (1 \le n \le 10^6) — the length of the string $s$.

In the second line of each input data set, there is a string $s$ of length $n$, consisting of characters $\text{A}$, $\text{B}$, and $\text{C}$.

It is guaranteed that the sum of $n$ across all input data sets of a single test does not exceed 10^6.

Output

For each set of input data, output on a separate line one integer — the maximum number of consecutive operations that can be performed on the string $s$.

Examples

Note

In the first set of input data from the first example, no more than $3$ consecutive operations can be performed on the string ABCCA. One example of how $3$ consecutive operations can be performed is [ABCCA $\to$ BACCA, BACCA $\to$ BACAC, BACAC $\to$ BAACC].

Scoring

Let $K$ be the sum of $n$ over all input data sets of one test.

1. ($2$ points): the answer is equal to $0$ or $1$;

2. ($3$ points): n \le 3;

3. ($5$ points): s_i \ne \texttt{C} for 1 \le i \le n;

4. ($5$ points): $s$ has the form \texttt{AA}\ldots \texttt{AABB}\ldots \texttt{BBCC}\ldots \texttt{CC} (that is, x \cdot \texttt{A} + y \cdot \texttt{B} + z \cdot \texttt{C} for certain positive $x$, $y$, $z$);

5. ($9$ points): s_is_{i+1} \ne \texttt{CA} for 1 \le i < n;

6. ($10$ points): T = 1, n \le 12;

7. ($8$ points): n \le 12;

8. ($28$ points): K \le 2000;

9. ($30$ points): without additional constraints.