题目描述

给你一个只包含字符 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

输入

5
4
ABBA
5
AAAAA
6
BBBBBB
7
ABABABA
20
AAABBBBBBBBAAABBBABA

输出

1333
12321
333333
1313212
33311111133121111311

说明/提示

• $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 自动生成