Description

给定一个由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成的字符串 $s$。

每次操作中，你可以选择字符串中两个相邻的元素 $s_is_{i+1}$，且它们的顺序为以下之一：$\texttt{AB}$、$\texttt{BC}$ 或 $\texttt{CA}$，然后交换它们的位置。

求可以对字符串 $s$ 进行的最大连续操作次数。

本题每个测试包含多组输入数据，你需要分别独立处理每组数据。

Input Format

第一行包含一个整数 $T$ $(1\le T\le 10^5)$ —— 输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 $n$ $(1 \le n \le 10^6)$ —— 字符串 $s$ 的长度。

每组数据的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成。

保证单个测试中所有数据的 $n$ 之和不超过 $10^6$。

Output Format

对于每组数据，输出一行一个整数 —— 可以对字符串 $s$ 进行的最大连续操作次数。

2
5
ABCCA
19
CCAABBBABBAAABBCCAA

3
28

Hint

在第一个样例的第一组数据中，字符串 $\texttt{ABCCA}$ 最多可以进行 $3$ 次连续操作。其中一种可能的操作序列是：$[\texttt{ABCCA} \rightarrow \texttt{BACCA}, \texttt{BACCA} \rightarrow \texttt{BACAC}, \texttt{BACAC} \rightarrow \texttt{BAACC}]$。

评分标准

设 $K$ 为单个测试中所有数据的 $n$ 之和。

• （$2$ 分）：答案为 $0$ 或 $1$；
• （$3$ 分）：$n \le 3$；
• （$5$ 分）：对于所有 $1 \le i \le n$，$s_i \ne \texttt{C}$；
• （$5$ 分）：$s$ 的形式为 $\texttt{AA}\ldots \texttt{AABB}\ldots \texttt{BBCC}\ldots \texttt{CC}$（即 $x \cdot \texttt{A} + y \cdot \texttt{B} + z \cdot \texttt{C}$，其中 $x$、$y$、$z$ 为正整数）；
• （$9$ 分）：对于所有 $1 \le i < n$，$s_is_{i+1} \ne \texttt{CA}$；
• （$10$ 分）：$T = 1$，$n \le 12$；
• （$8$ 分）：$n \le 12$；
• （$28$ 分）：$K \le 2000$；
• （$30$ 分）：无额外限制。

翻译由 DeepSeek V3 完成