题目描述

题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day2 T3. Розворот ABC

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

在一次操作中，你可以选择字符串中两个相邻的字符 $s_i s_{i+1}$，如果它们的顺序是 AB、BC 或 CA，则可以将它们交换位置。

你需要找出可以对字符串 $s$ 执行的最大连续操作次数。

在本题中，每个测试点包含多个输入数据组。你需要为每个数据组独立解决问题。

输入格式

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

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

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

保证所有数据组中 $n$ 的总和不超过 $10^6$。

输出格式

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

2
5
ABCCA
19
CCAABBBABBAAABBCCAA

3
28

在第一个样例的第一个数据组中，对于字符串 ABCCA，最多可以执行 $3$ 次连续操作。一个可能的操作序列为：[ABCCA $\to$ BACCA, BACCA $\to$ BACAC, BACAC $\to$ BAACC]。

数据范围与提示

设 $K$ 为单个测试中所有数据组的 $n$ 之和。详细子任务附加限制及分值如下表所示：