問題文

A, B, C からなる長さ $N$ の文字列 $S$ が与えられます。

Alice さんと Bob さんは、$S$ を使って以下のようなゲームを行います。

Alice さんが先手、Bob さんが後手となり、以下のいずれかの操作を一つ選んで行うことを交互に繰り返します。

• 相手が選んだことのない $1$ 以上 $N$ 以下の整数 $i$ を一つ選び、以下のような置換を行う。
• $S$ の $i$ 文字目が A であったとき B に置き換える。
• $S$ の $i$ 文字目が B であったとき C に置き換える。
• $S$ の $i$ 文字目が C であったとき A に置き換える。

• 終了宣言を行う。

いずれかのプレイヤーが終了宣言をした、または両方のプレイヤーがそれぞれ $10^{100}$ 回ずつ操作を行った時点でゲームは終了します。

Alice さんの目標は、ゲーム終了時点の $S$ を辞書順でできるだけ小さくすることです。
逆に Bob さんの目標は、ゲーム終了時点の $S$ を辞書順でできるだけ大きくすることです。

双方が最善を尽くした$\color{red}^{*1}$ときにおける、ゲーム終了時点の $S$ を求めてください。

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

制約

• $1 \leq T \leq 10^4$
• $T$ は整数である。
• 各テストケースについて、以下の制約をすべて満たす。
• $1 \leq N \leq 5 \times 10^5$
• $N$ は整数である。
• $S$ は A, B, C からなる長さ $N$ の文字列である。
• 一つの入力ファイルにおける $N$ の総和は $5 \times 10^5$ 以下である。

入力

入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_t ~ (1 \leq t \leq T)$ は $t$ 番目のテストケースを表します。

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

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

$N$
$S$

出力

$T$ 行出力し、$t$ 行目には $t$ 番目のテストケースについての答えを出力してください。

サンプル

2
3
ABC
5
CBABC

ABC
ACABC