题目描述

给定一个由大写字母 A、B、C 组成的、长度为 $N$ 的字符串 $S$。

你可以对 $S$ 进行任意多次（包括 $0$ 次）如下两种操作，顺序任意：

• 选择 $S$ 中的一个字符 A，把它替换为 BB（字符串长度增加 $1$）；
• 选择 $S$ 中相邻的两个字符 BB，把它们替换为一个字符 A（字符串长度减少 $1$）。

请求出所有操作结束后 $S$ 可能变成的字符串中，字典序最小的一个。

两个字符串的字典序比较规则：从前向后逐位比较，第一处不同的字符按 A < B < C 的顺序分出大小；若其中一个是另一个的前缀，则更短的那个更小。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

接下来依次给出 $T$ 组数据，每组两行：

• 第一行一个正整数 $N$（$1\le N\le 2\times 10^5$），表示字符串的长度；
• 第二行一个长度为 $N$ 的字符串 $S$，仅由大写字母 A、B、C 组成。

同一个测试点内保证 $\sum N\le 5\times 10^5$，$T\le 2\times 10^4$。更精确的限制见子任务表。

输出格式

对每组数据输出一行一个字符串，表示能得到的字典序最小的字符串。

3
4
CBAA
1
A
6
BBBCBB

CAAB
A
ABCA

6
2
BA
3
BBA
3
CBB
4
BACA
5
CCABB
1
B

AB
AA
CA
ABCA
CCAA
B

样例解释

样例 1 第 1 组：可以按如下方式操作：CBAA $\to$ CBBBA（第 $3$ 个字符 A 换成 BB）$\to$ CABA（第 $2,3$ 个字符 BB 换成 A）$\to$ CABBB $\to$ CAAB。可以验证无法得到比 CAAB 更小的字符串。

样例 2：六组的答案依次为 AB、AA、CA、ABCA、CCAA、B。注意答案可能比原串短（如第 $2$ 组 BBA 长度 $3$ 变为 $2$），也可能与原串完全相同（如第 $6$ 组）。

数据范围

下发文件

对于 $100\%$ 的数据：$1\le T\le 2\times 10^4$，$1\le N\le 2\times 10^5$，$\sum N\le 5\times 10^5$，$S$ 仅由大写字母 A、B、C 组成。

下发文件见 sample.zip，其中 sample1、sample2 为上述两组样例，sample{i}_1 对应子任务 $i$ 的一个样例。

本题共 $5$ 个子任务，合计 $100$ 分，共 $20$ 个测试点，每点 $5$ 分，没有子任务依赖。

时间限制 $2$ 秒，空间限制 $256$ MiB。