問題文

N 個の石が左右一列に並んでいます。各石は A, B, C のいずれかの色で塗られており、左から i 番目 (1\le i\le N) の石の色は S_i です。

Alice と Bob がこの石の列を使って以下のようなゲームを行います。

• Alice から始めて両者は交互に手番をプレイする。
• 各手番では、プレイヤーは色の異なる 2 つの隣接する石を選び、それらを列から取り除く。その後、同じ場所に色 A, B, C のうち取り除いたどちらの石とも異なる色の石を 1 つ挿入する。

先に手番をプレイできなくなったプレイヤーの負けです。

両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

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

制約

• 1\le T\le 2\times 10^4
• 1\le N\le 2\times 10^5
• S_i は A, B, C のいずれか
• 全てのテストケースにおける N の総和は 2\times 10^5 以下

入力例 1

3
3
ABC
4
AAAA
10
AACBACBABC

出力例 1

Alice
Bob
Alice

1 番目のテストケースについて考えます。

例えばゲームは以下のように進行します：

• Alice の手番：左から 1,2 番目の石を取り除き、色 C の石を挿入する。石の列は CC となる。
• Bob は手番をプレイできないので、Alice の勝利である。

Bob がどのように行動しても Alice が適切に行動することで Alice が必ず勝利することができます。