This editorial assumes knowledge of Grundy numbers.

Consider the following game:

There is a pile of \(x\) stones. Starting from Alice, the players alternately take at least \(1\) and at most \(K\) stones. The player who cannot take stones first loses.

It is known that the Grundy number of this game is \(g(x) = x \bmod (K+1)\). This can also be easily proved by induction.

Let \(S\) be the multiset of \(g(A_{i,j})\) for each \((i,j)\) where \(i+j\) is odd.

In fact, Bob winning this game is equivalent to \(\displaystyle \bigoplus_{x \in S} x = 0\). We prove this.

[1] When \(\displaystyle \bigoplus_{x \in S} x = 0\)

It suffices to show that any operation results in \(\displaystyle \bigoplus_{x \in S} x \neq 0\).

If a cell \((i,j)\) where \(i+j\) is even is chosen and operated on, one value in \(S\) changes. By the properties of XOR, since the total XOR was originally \(0\), it cannot remain \(\displaystyle \bigoplus_{x \in S} x = 0\).

The same argument applies when a cell \((i,j)\) where \(i+j\) is odd is chosen and operated on, since one value in \(S\) changes as well.

[2] When \(\displaystyle \bigoplus_{x \in S} x \neq 0\)

By the same argument as in ordinary Nim, there always exists an operation that makes \(\displaystyle \bigoplus_{x \in S} x = 0\).

From the above, we should output Bob if the total XOR of \(g(A_{i,j})\) over all \((i,j)\) where \(i+j\) is odd equals \(0\), and Alice otherwise.

By implementing the above appropriately, you can solve this problem.

Implementation example (Python3)

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    res = 0
    for i in range(n):
        for j in range(n):
            if (i + j) % 2 == 1:
                res ^= a[i][j] % (k + 1)
    print("Alice" if res != 0 else "Bob")

Proposed by: kyopro_friends