Problem Statement

There is an $N \times N$ grid. The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $(i,j)$. Cell $(i,j)$ initially contains $A_{i,j}$ stones.

Alice and Bob play the following game using this grid.

• Starting with Alice, the two players alternate taking turns.
• On each turn, the player chooses a cell and moves at least $1$ and at most $K$ stones from it together to an adjacent cell above or to the left. Specifically, the following steps are performed in order:
• Choose a cell $(i,j)$ that contains at least $1$ stone. Cell $(1,1)$ cannot be chosen.
  • Let $c$ be the number of stones in cell $(i,j)$, and choose an integer $x$ satisfying $1 \le x \le \min(c,K)$.
  • Choose as the destination either cell $(i-1,j)$ (if it exists) or cell $(i,j-1)$ (if it exists), then remove $x$ stones from cell $(i,j)$ and move all of them to that cell.

The player who cannot take a turn first loses.

Determine which player wins when both play optimally.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T$
• $2\le N\le 100$
• $1\le K\le 10^9$
• $0\le A_{i,j}\le 10^9$
• The sum of $N^2$ over all test cases is at most $3\times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

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}

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, output Alice if Alice wins when both play optimally, and Bob if Bob wins.