Alice と Bob は、1列に並んだいくつかのマス目からなるボード上でゲームをしています。いくつかのマス（0個の場合もある）には、プレイヤーの名前である "Alice" または "Bob" が書かれています。その他のマスは最初は空です。

Alice から始めて、2人のプレイヤーは交互に手番を行います。自分の手番において、プレイヤーは自分の名前が書かれたマスと隣接していない空のマスを1つ選び、そのマスに自分の名前を書き込みます。なお、隣接するマスに相手の名前が書かれているかどうかは関係ありません。

手番で動けなくなったプレイヤーが負けとなります。ボードの初期状態が与えられたとき、両者が最善を尽くした場合に Alice と Bob のどちらが勝つかを判定してください。

入力

入力は1つ以上のテストケースを含みます。入力の最初の行には、テストケースの数を示す整数 $t$ ($1 \le t \le 2 \times 10^5$) が含まれます。続いて $t$ 個のテストケースが以下の形式で与えられます。

$n$ $s$

整数 $n$ はボードのマス目の数を表します ($1 \le n \le 2 \times 10^5$)。ボードの初期状態は長さ $n$ の文字列 $s$ として与えられます。

各 $i$ ($1 \le i \le n$) について、$s$ の $i$ 番目の文字 $s_i$ は 'a'、'b'、または '.' であり、左から $i$ 番目のマスの初期状態を表します。ここで、$s_i$ が 'a' ならばそのマスには Alice という名前が、$s_i$ が 'b' ならば Bob という名前が書かれており、'.' ならばそのマスは空であることを示します。

初期状態のボードにおいて、同じ名前が書かれたマス同士が隣接することはないことが保証されています。

すべてのテストケースにおける $n$ の総和は $2 \times 10^5$ を超えません。

出力

各テストケースについて、Alice が勝つ場合は alice を、Bob が勝つ場合は bob を1行で出力してください。

入出力例

入力 1

3
2
..
3
.a.
4
ab..

出力 1

bob
bob
alice