题目描述

给定一个只包含 A 和 B 的长度为 $n\ (2\leq n)$ 的字符串 $T=T_1T_2\dots T_n$，定义长度为 $n-1$ 的字符串 $f(T)$ 如下：

• 设所有满足 $T_i=$A 的 $i\ (1\leq i \leq n-1)$ 记为 $a_1 < a_2 < \dots < a_m$，所有满足 $T_i=$B 的 $i\ (1\leq i \leq n-1)$ 记为 $b_1 < b_2 < \dots < b_k$。则 $f(T)=T\_{a\_1+1}T\_{a\_2+1}\dots T\_{a\_m+1}T\_{b\_1+1}T\_{b\_2+1}\dots T\_{b\_k+1}$。

例如，对于字符串 $T=$ABBABA，满足 $T_i=$A 的 $i$ 有 $i=1,4$，满足 $T_i=$B 的 $i$ 有 $i=2,3,5$，因此 $f(T)=T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}=$BBBAA。

现在给定一个只包含 A 和 B 的长度为 $N$ 的字符串 $S$。

请你对 $S$ 连续执行 $N-1$ 次 $f(S)$ 操作，输出最终得到的 $S$。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组数据格式如下：

$N$ $S$

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例 1

输入

3
2
AB
3
AAA
4
ABAB

输出

B
A
A

说明/提示

数据范围

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 3 \times 10^5$
• $S$ 是只包含 A 和 B 的长度为 $N$ 的字符串
• 输入的所有 $N$ 之和不超过 $3 \times 10^5$
• 所有输入的数均为整数

样例解释 1

对于第 $1$ 组测试数据，$S$ 从 AB 变为 B。
对于第 $2$ 组测试数据，$S$ 从 AAA 变为 AA，再变为 A。
对于第 $3$ 组测试数据，$S$ 从 ABAB 变为 BBA，再变为 BA，再变为 A。

由 ChatGPT 4.1 翻译