A - Right Side Character 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400

問題文

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\ (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 が与えられます。

Sf(S) で置き換えることを N-1 回行った後の S を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 3 \times 10^5
  • SA,B のみからなる長さ N の文字列
  • 入力される数値はすべて整数
  • 1 つの入力に含まれるテストケースについて、 N の総和は 3 \times 10^5 以下

入力

入力は以下の形式で標準入力から与えられます。

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

各ケースは以下の形式で与えられます。

N
S

出力

T 行出力してください。i 行目には i 番目のテストケースに対する答えを出力してください。


入力例 1

3
2
AB
3
AAA
4
ABAB

出力例 1

B
A
A

1 つ目のテストケースについて、SAB{}\rightarrow {}B と変化します。

2 つ目のテストケースについて、SAAA{} \rightarrow {}AA{} \rightarrow {}A と変化します。

3 つ目のテストケースについて、SABAB{}\rightarrow {}BBA{} \rightarrow {}BA{} \rightarrow {}A と変化します。

Score : 400 points

Problem Statement

For a string T=T_1T_2\dots T_n of length n\ (2\leq n) consisting of A and B, we define a string f(T) of length n-1 as follows.

  • Let a_1 < a_2 < \dots < a_{m} be the indices i\ (1\leq i \leq n-1) such that T_i={}A, and b_1 < b_2 < \dots < b_k be the indices i\ (1\leq i \leq n-1) such that T_i={}B. Then, let 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}.

For example, for the string T={}ABBABA, the indices i\ (1\leq i \leq 5) with T_i={}A are i=1,4, and the indices i\ (1\leq i \leq 5) with T_i={}B are i=2,3,5, so f(T) is T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA.

You are given a string S of length N consisting of A and B.

Find S after replacing S with f(S) (N-1) times.

You have T test cases to solve.

Constraints

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 3 \times 10^5
  • S is a string of length N consisting of A and B.
  • All numbers in the input are integers.
  • The sum of N over the test cases in a single input file is at most 3 \times 10^5.

Input

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

N
S

Output

Print T lines. The i-th line should contain the answer to the i-th test case.


Sample Input 1

3
2
AB
3
AAA
4
ABAB

Sample Output 1

B
A
A

In the first test case, S changes as AB{}\rightarrow {}B.

In the second test case, S changes as AAA{} \rightarrow {}AA{} \rightarrow {}A.

In the third test case, S changes as ABAB{}\rightarrow {}BBA{} \rightarrow {}BA{} \rightarrow {}A.