Optimal Grid Game Winner

In this problem, Alice and Bob play a game on a grid of size \(m \times n\). Each cell of the grid is either empty, denoted by a dot ('.'), or blocked, denoted by a hash ('#'). Initially, some cells might be blocked. Both players play optimally and take turns. Alice always starts first.

Let \(E\) be the total number of empty cells in the grid. The rules to determine the winner are as follows:

• If \(E=0\), i.e. the grid has no empty cells, the game is declared a Draw.
• If \(E\) is odd (i.e. \(E \bmod 2 = 1\)), then Alice wins.
• If \(E\) is even and \(E>0\), then Bob wins.

Your task is to determine the outcome of the game for each test case based on the grid configuration given in the input.

inputFormat

The first line of input contains a single integer \(t\) denoting the number of test cases. For each test case, the first line contains two integers \(m\) and \(n\) representing the number of rows and columns of the grid respectively. This is followed by \(m\) lines, each containing a string of length \(n\) consisting only of characters '.' and '#', which represent the grid configuration.

Example:

1
3 3
...
.#.
###

outputFormat

For each test case, output a single line containing one of the following: "Alice", "Bob", or "Draw" - the winner of the game based on the rules described.

1
3 3
...
.#.
###

Alice