AT_arc219_d [ARC219D] Grid Game

$ N $ 行 $ N $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と表します。マス $ (i,j) $ にははじめ $ A_{i,j} $ 個の石があります。 Alice と Bob がこのグリッドを使って以下のようなゲームを行います。 - Alice から始めて両者は交互に手番をプレイする。 - 各手番では、プレイヤーはマスを $ 1 $ つ選び、そこから $ 1 $ 個以上 $ K $ 個以下の石をまとめて上または左に隣接するマスへ移動させる。具体的には、次の手順を順に行う。 1. 石が $ 1 $ 個以上あるマス $ (i,j) $ を選ぶ。ただし、マス $ (1,1) $ は選べない。 2. マス $ (i,j) $ にある石の個数を $ c $ とし、 $ 1 \le x \le \min(c,K) $ を満たす整数 $ x $ を選ぶ。 3. 移動先として、存在するならばマス $ (i-1,j) $ またはマス $ (i,j-1) $ のいずれか一方を選び、マス $ (i,j) $ から石を $ x $ 個取り出して全てそのマスに移動させる。 先に手番をプレイできなくなったプレイヤーの負けです。 両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ A_{1,1} $ $ A_{1,2} $ $ \ldots $ $ A_{1,N} $ $ A_{2,1} $ $ A_{2,2} $ $ \ldots $ $ A_{2,N} $ $ \vdots $ $ A_{N,1} $ $ A_{N,2} $ $ \ldots $ $ A_{N,N} $

各テストケースに対する答えを順に改行区切りで出力せよ。 各テストケースについて、両者が最善を尽くしたとき Alice が勝つならば `Alice` を、Bob が勝つならば `Bob` を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 例えばゲームは以下のように進行します（両者が最適に手番をプレイしているとは限らないことに注意してください）： - Alice の手番：マス $ (2,2) $ を選び、石を $ 2 $ 個取り出す。取り出した石をマス $ (1,2) $ に移動させる。 - Bob の手番：マス $ (1,2) $ を選び、石を $ 2 $ 個取り出す。取り出した石をマス $ (1,1) $ に移動させる。 - Alice の手番：マス $ (2,1) $ を選び、石を $ 2 $ 個取り出す。取り出した石をマス $ (1,1) $ に移動させる。 - Bob の手番：マス $ (2,1) $ を選び、石を $ 1 $ 個取り出す。取り出した石をマス $ (1,1) $ に移動させる。 - Alice の手番：マス $ (1,2) $ を選び、石を $ 1 $ 個取り出す。取り出した石をマス $ (1,1) $ に移動させる。 - Bob の手番：Bob は手番をプレイできないので負けである。 Alice は最善を尽くすことで必ず Bob に勝つことができます。したがって、 $ 1 $ 行目には `Alice` を出力してください。 ### Constraints - $ 1\le T $ - $ 2\le N\le 100 $ - $ 1\le K\le 10^9 $ - $ 0\le A_{i,j}\le 10^9 $ - 全てのテストケースにおける $ N^2 $ の総和は $ 3\times 10^5 $ 以下 - 入力される値は全て整数