これはインタラクティブ問題である。

アリスとボブは、バイナリ文字列 $s$ と固定された整数 $k$ を使ってゲームを行う。最初、空文字列 $t$ がある。プレイヤーはアリスから始めて、交互に $t$ の末尾に文字（'0' または '1'）を追加する。

インタラクションは、$t$ にちょうど $k$ 文字が追加されるまで続く。アリスは、最終的な文字列 $t$ が $s$ を連続した部分文字列として含む場合にのみ勝利し、そうでなければボブが勝利する。

あなたはアリスまたはボブのどちらかとしてプレイすることを選択できる。目的は審判に対してゲームに勝つことである。

インタラクション

各テスト実行には複数のテストケースが含まれる。最初に、テストケースの数 $T$ ($1 \le T \le 100$) を表す整数を含む行を読み取るべきである。

各テストケースでは、まず 1 行にバイナリ文字列 $s$ と整数 $k$ ($1 \le |s| \le k \le 100$) を読み取ってインタラクションを開始する。これはゲームのラウンド数とパラメータを示す。 その後、1 単語を出力する: アリスとしてプレイする場合は Alice、ボブとしてプレイする場合は Bob。 その後、空文字列からゲームが始まる。アリスが最初の手を行う。あなたの手番のときは、1 文字 (0 または 1) を出力する。審判の手番のときは、1 文字 (0 または 1) を読み取る。 ゲームは現在の文字列の長さが $k$ になった時点で終了する。

出力操作のたびに、出力バッファをフラッシュしなければならない。例えば、C++ では cout << endl; または cout.flush(); を使用できる。

不正なトークンを出力した場合、ゲーム終了後に手を打った場合、フラッシュしなかった場合、またはゲームに負けた場合、Wrong Answer となる。

注記

次の表は、サンプルに対する可能なインタラクションを示している。"審判" 列の行は参加者のプログラムが読み取るものであり、"参加者" 列の行は参加者のプログラムが出力するものである。