2025_2C. Reversal ABC
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ consisting of characters $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{C}$$$.

In one operation, you are allowed to choose two adjacent elements of the string $$$s_is_{i+1}$$$ that are in the following order: $$$\texttt{AB}$$$, $$$\texttt{BC}$$$, or $$$\texttt{CA}$$$, and swap them.

Find the maximum number of consecutive operations that can be performed on the string $$$s$$$.

In this problem, each test contains several sets of input data. You need to solve the problem independently for each such set.

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 $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{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$$$.

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 \lt 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.
Example
Input
2
5
ABCCA
19
CCAABBBABBAAABBCCAA
Output
3
28
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 $$$\rightarrow$$$ BACCA, BACCA $$$\rightarrow$$$ BACAC, BACAC $$$\rightarrow$$$ BAACC].