Alice と Bob は、文字 A と B のみからなる単語を用いてしりとりを行います。
使用できる単語は、先頭の文字と末尾の文字によって次の \(4\) 種類に分類されます。 それぞれの種類の単語数は次の通りです。
それぞれの単語は、ゲーム中に高々一度しか使用できません。
ゲームは Alice の手番から始まり、Alice と Bob は交互に、まだ使用されていない単語を \(1\) つ選んで宣言します。
最初の手番では、Alice は先頭の文字が A である単語を選ばなければなりません。 それ以降の手番では、直前に宣言された単語の末尾の文字と、先頭の文字が等しい単語を選ばなければなりません。
条件を満たす単語を宣言できないプレイヤーの負けです。
Alice と Bob がともに最適に行動するとき、勝者を求めてください。
\(T\) 個のテストケースが与えられるので、それぞれについて答えてください。
入力は以下の形式で標準入力から与えられます。
| \(T\) | |
| \(AA_1~AB_1~BA_1~BB_1\) | |
| \(AA_2~AB_2~BA_2~BB_2\) | |
| \(\vdots\) | |
| \(AA_T~AB_T~BA_T~BB_T\) |
制約は以下の通りです。
\(T\) 行出力してください。 \(i\) 行目には、\(i\) 番目のテストケースで Alice が勝つなら Alice を、Bob が勝つなら Bob を出力してください。
30 1 1 01 0 0 02 3 3 4
Bob Alice Bob
サンプルの \(1\) 番目のテストケースについて:
Alice が最初に宣言できる単語は AB 型の単語のみです。 その後 Bob は BA 型の単語を宣言でき、Alice は単語を宣言できなくなるため、Bob が勝ちます。
サンプルの \(2\) 番目のテストケースについて:
Alice は AA 型の単語を宣言します。 その後 Bob が宣言できる単語は残っていないため、Alice が勝ちます。
サンプルの \(3\) 番目のテストケースについて:
Alice がどのように行動しても Bob が勝ちます。