题目描述

给定一个由 A 和 B 组成的长度为 $n\ (2 \leq n)$ 的字符串 $T=T_1T_2\dots T_n$，我们定义一个长度为 $n-1$ 的字符串 $f(T)$ 如下。

• 设 $a_1 < a_2 < \dots < a_{m}$ 是满足 $T_i={}$A 的下标 $i\ (1\leq i \leq n-1)$ 的集合，$b_1 < b_2 < \dots < b_k$ 是满足 $T_i={}$B 的下标 $i\ (1\leq i \leq n-1)$ 的集合。那么，令 $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\ (1\leq i \leq 5)$ 是 $i=1,4$，满足 $T_i={}$B 的下标 $i\ (1\leq i \leq 5)$ 是 $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$ 在用 $f(S)$ 替换 $S$ $(N-1)$ 次后的结果。

你需要解决 $T$ 个测试用例。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 3 \times 10^5$
• $S$ 是一个由 A 和 B 组成的长度为 $N$ 的字符串。
• 输入中的所有数字都是整数。
• 在单个输入文件中，所有测试用例中 $N$ 的总和至多为 $3 \times 10^5$。

输入

输入以以下格式从标准输入给出：

$T$ $case_1$ $\vdots$ $case_T$

每个测试用例按以下格式给出：

$N$ $S$

输出

输出 $T$ 行。第 $i$ 行应该包含第 $i$ 个测试用例的答案。

示例输入 1

3
2
AB
3
AAA
4
ABAB

示例输出 1

B
A
A

在第一个测试用例中，$S$ 变为 AB${} \rightarrow {}$B。

在第二个测试用例中，$S$ 变为 AAA${} \rightarrow {}$AA${} \rightarrow {}$A。

在第三个测试用例中，$S$ 变为 ABAB${} \rightarrow {}$BBA${} \rightarrow {}$BA${} \rightarrow {}$A。