AT_arc179_f [ARC179F] All the Same

给你一个只包含字符 `A` 和 `B` 的长度为 $N$ 的字符串 $S$。 需要找到一个由字符 `1`、`2` 和 `3` 组成的长度为 $N$ 的字符串 $X$，并定义其**得分**如下： - 初始化四个变量 $h_1, h_2, h_3, P$ 为 $0$。 - 然后依次处理 $i = 1, 2, \dots, N$： - 若 $S$ 的第 $i$ 个字符为 `A`，则执行操作 A；若为 `B`，则执行操作 B。此处，$d$ 代表 $X$ 的第 $i$ 个字符对应的数字。 - **操作 A**：将 $h_d$ 增加 $2$。 - **操作 B**：若 $d$ 等于 $2$ 或 $h_d$ 不等于 $h_2$，则将 $P$ 设为 $-10^{100}$；否则将 $h_d$ 和 $h_2$ 各自增加 $1$。 - 如果此时 $h_1$ 等于 $h_2$ 且等于 $h_3$，则将 $P$ 增加 $1$。 - 最终，$P$ 的值即为字符串 $X$ 的得分。 请输出一个能使得分最大的字符串 $X$。 共有 $T$ 个测试用例，请分别求解每个测试用例。

输入包含多组测试数据，第一行为整数 $T$，表示测试用例的个数。 每个测试用例包括两行： 第一行为整数 $N$，表示字符串 $S$ 的长度。 第二行是长度为 $N$ 的字符串 $S$。

输出共 $T$ 行，每行表示一个测试用例的结果。 第 $i$ 行输出第 $i$ 个测试用例中得到最高得分的字符串 $X$。 如有多种可能的结果，输出任意一种均可。

- $1 \le T \le 10^5$ - $1 \le N \le 10^6$ - $S$ 由字符 `A` 和 `B` 组成 - 所有测试用例中的 $N$ 之和不超过 $10^6$ ## 样例解释 以每个字符的处理步骤举例说明变量 $(h_1, h_2, h_3, P)$ 的变化： - 第一个测试用例处理结果为 $(0, 0, 0, 0) \rightarrow (2, 0, 0, 0) \rightarrow (2, 1, 1, 0) \rightarrow (2, 2, 2, 1) \rightarrow (2, 2, 4, 1)$，所以最大得分为 $1$。 - 第二个测试用例处理结果为 $(0, 0, 0, 0) \rightarrow (2, 0, 0, 0) \rightarrow (2, 2, 0, 0) \rightarrow (2, 2, 2, 1) \rightarrow (2, 4, 2, 1) \rightarrow (4, 4, 2, 1)$，最大得分为 $1$。 - 第三个、第四个和第五个测试用例的得分最大值分别为 $0, 0, 2$。 注意，一个测试用例可能会存在多个得分最大的 $X$，选择其中任意一个输出即可。 **本翻译由 AI 自动生成**