给定一个仅由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成的字符串 $s$。
在一次操作中，你可以选择字符串中两个相邻的元素 $s_is_{i+1}$，前提是它们的顺序是以下之一：$\texttt{AB}$、$\texttt{BC}$ 或 $\texttt{CA}$，并交换它们。
请找出字符串 $s$ 上最多可以连续进行多少次这样的操作。
本题中，每组测试包含若干组输入数据。你需要分别独立地解决每组输入数据。
输入
第一行包含一个整数 $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$。
输出
对于每组输入数据，在单独的一行输出一个整数~--- 字符串 $s$ 上最多可以连续进行的操作次数。
示例
输入
2 5 ABCCA 19 CCAABBBABBAAABBCCAA
输出
3 28
说明
在第一个样例的第一组输入中，字符串 $\texttt{ABCCA}$ 最多只能进行 $3$ 次连续操作。以下是一个能进行 $3$ 次操作的例子：[$\textbf{AB}\texttt{CCA}$ $\rightarrow$ $\texttt{BACCA}$, $\texttt{BAC}\textbf{CA}$ $\rightarrow$ $\texttt{BACAC}$, $\texttt{BA}\textbf{CA}\texttt{C}$ $\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}$（即由若干个 $\texttt{A}$、若干个 $\texttt{B}$ 和若干个 $\texttt{C}$ 拼接而成）；
- （$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$ 分）：无额外限制。