Problem Statement

You are given a string $S$ of length $N$ consisting of A, B, C.

Alice and Bob play the following game using $S$.

Alice moves first and Bob moves second, and they alternately repeat choosing and performing one of the following operations.

• Choose one integer $i$ between $1$ and $N$, inclusive, that the opponent has never chosen, and perform the following replacement.
• If the $i$-th character of $S$ is A, replace it with B.
• If the $i$-th character of $S$ is B, replace it with C.
• If the $i$-th character of $S$ is C, replace it with A.

• Declare the end of the game.

The game ends as soon as either player declares the end, or both players have each performed $10^{100}$ operations.

Alice's goal is to make $S$ at the end of the game as lexicographically small as possible.
Conversely, Bob's goal is to make $S$ at the end of the game as lexicographically large as possible.

Find $S$ at the end of the game when both players play optimally$\color{red}^{*1}$.

You are given $T$ test cases; answer each of them.

Constraints

• $1 \leq T \leq 10^4$
• $T$ is an integer.
• Each test case satisfies all of the following constraints.
• $1 \leq N \leq 5 \times 10^5$
• $N$ is an integer.
• $S$ is a string of length $N$ consisting of A, B, C.
• The sum of $N$ in a single input file is at most $5 \times 10^5$.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_t ~ (1 \leq t \leq T)$ denotes the $t$-th test case.

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

Each test case is given in the following format.

$N$
$S$

Output

Print $T$ lines. The $t$-th line should contain the answer for the $t$-th test case.

Sample

2
3
ABC
5
CBABC

ABC
ACABC